题解 P1331 【海战】

2018-05-14 18:10:39


典型染色搜索求联通块,问题是怎样才能判断Bad placement?

以联通块最左上角的地方作为矩阵的左上角,然后计算矩形长宽(假设它是矩形),在由左上角,长,宽(left,top,width,height)构成的矩形里判断。

如果矩形中有一个不是相应颜色的(或者是海洋的),那么直接KO,否则,判断这个矩阵的面积和染色面积的区别,如果不一样那么就goodbye了,否则ans++;最后如果没有挂就输出ans。

似乎该上代码了:

#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;
}