题解 P1331 【海战】

典型染色搜索求联通块，问题是怎样才能判断Bad placement? 以联通块最左上角的地方作为矩阵的左上角，然后计算矩形长宽（假设它是矩形），在由左上角，长，宽(left,top,width,height)构成的矩形里判断。 如果矩形中有一个不是相应颜色的（或者是海洋的），那么直接KO，否则，判断这个矩阵的面积和染色面积的区别，如果不一样那么就goodbye了，否则ans++；最后如果没有挂就输出ans。 似乎该上代码了： ```cpp #include <bits/stdc++.h> using namespace std; int n,m,dx[] = {1,0,-1,0},dy[] = {0,1,0,-1},clr[1005][1005],ans,cnt[1000005]; char a[1005][1005]; bool vis[1000005]; void dfs(int x,int y,int clnum)//位置和颜色 { clr[x][y] = clnum;++cnt[clnum];//有几个方块染这个颜色，就是染色面积 for (int i = 0;i < 4;i++) { int nx = x + dx[i],ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || clr[nx][ny] || a[nx][ny] == '.') continue;//出界 dfs(nx,ny,clnum); } } int main () { scanf("%d%d",&n,&m); for (int i = 0;i < n;i++) scanf("%s",a[i]); int clnum = 0; for (int i = 0;i < n;i++) for (int j = 0;j < m;j++) if (clr[i][j] == 0 && a[i][j] == '#') dfs(i,j,++clnum);//染色标配，海洋颜色为0 for (int i = 0;i < n;i++) for (int j = 0;j < m;j++) { if (clr[i][j] == 0 || vis[clr[i][j]]) continue;//vis：是不是左上角？ int l = 0,w = 0; while (clr[i + l][j] == clr[i][j] && i + l < n) ++l;/计算长 while (clr[i][j + w] == clr[i][j] && j + w < m) ++w;//计算宽 bool valid = 1; for (int k = 0;k < l;k++) for (int o = 0;o < w;o++) if (clr[k + i][o + j] == 0) { valid = 0;break;//KO } valid = valid && (cnt[clr[i][j]] == l * w);//goodbye if (!valid) { printf("Bad placement.");return 0;//直接退出 } ans++; vis[clr[i][j]] = 1;//左上角被用了 } printf("There are %d ships.",ans); return 0; } ```