#include char data[1002][1002]; char checkok[1002][1002]; void getlen(int x, int y, int *xL, int *yL) { int j, ok, i = x; while (data[i][y] == '#') i++; *xL = i - x; i = y; while (data[x][i] == '#') i++; *yL = i - y; ok = (1 ==1); for (i = 0; (i < *xL) && ok; i++) for (j = 0; (j < *yL) && ok; j++) ok &= (data[x+i][y+j] == '#'); if (!ok) { *xL = 1; *yL = 1; } } int check(int x1, int y1, int x2, int y2) { int i; x1--; y1--; x2++;y2++; int ok = (1==1); for (i = x1; i <= x2 && ok; i++) ok = (data[i][y1] == '.') && (data[i][y2] == '.'); for (i = y1; i <= y2 && ok; i++) ok = (data[x1][i] == '.') && (data[x2][i] == '.'); return ok; } void setok(int x1, int y1, int x2, int y2) { int i,j; for (i = x1; i <= x2; i++) for (j = y1; j <= y2; j++) checkok[i][j] = 'O'; } int ships; void printok(int x, int y) { int i,j; for (i = 0; i <= x+1; i++) { for (j = 0; j <= y+1; j++) printf("%c", checkok[i][j]); printf("\n"); } } int test(int R, int C) { int r, c, xL, yL; int ch; ships = 0; for (r = 1; r <= R+1; r++) for (c= 1; c <= C+1; c++) { if ((checkok[r][c] != 'O' && data[r][c] == '#')) { getlen(r, c, &xL, &yL); // printf("Getlen %d %d", xL, yL); ships ++; ch = check(r, c, r + xL -1, c + yL -1); if (!ch) return ch; setok(r,c,r+xL-1, c+yL-1); } // printok(R,C); } return 1; } void printit(int x, int y) { int i,j; for (i = 1; i < x+1; i++) { for (j = 1; j < y+1; j++) printf("%c", data[i][j]); printf("\n"); } } int main (void) { int i, j, R, C; char ch; scanf("%d %d", &R, &C); while (R != 0 && C != 0) { for (i = 0; i <= R + 1; i++) for (j=0; j<= C+1; j++) data[i][j] = '0'; for (i = 1; i < R + 1; i++) scanf("%s", data[i] + 1); for (i = 0; i <= R + 1; i++) { data[i][0] = '.'; data[i][C+1] = '.'; } for (i = 0; i <= C+1; i++) { data[0][i] = '.'; data[R+1][i] = '.'; } // printit(R,C); ch = test(R,C); if (ch) printf("There are %d ships.\n", ships); else printf("Bad placement.\n"); for (i = 0; i <= R + 1; i++) for (j=0; j <= C + 1; j++) checkok[i][j] = 'x'; scanf("%d %d", &R, &C); } return 0; }