【简单dfs】Bubble Cup 14

传送门  Problem - 1600J - Codeforces

题目  

 

题意

给定n行m列， 求每个连通块由多少格子组成，并将格子数从大到小排序输出

对于每个格子都有一个数（0~15），将其转化为二进制（四位数），比如1010

表示北为1，不可通；东为0，可通；南为1，不可通；西为0，可通。

即 1表示墙，不可通，四位数字依次表示为北东南西

【注意：比如样例9到14去，只需判断9东边是否可通即可，14不用管】

题解

差不多和dfs的板子一样~

AC代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e3+10;

int n, m, res[N*N], idx = -1, step;
int dx[4] = {0,1,0,-1}, dy[4] =  {-1,0,1,0};//西南东北
bool book[N][N];
int a[N][N];

void dfs(int x, int y)
{
    bool flag = 0;
    int xx = a[x][y];
    for(int i = 0; i < 4; i ++)
    {
        if((xx>>i)&1==1)    continue;
        
        int tx = x+dx[i];
        int ty = y+dy[i];
        if(tx<0||tx>=n||ty<0||ty>=m)    continue;
            
        if(!book[tx][ty])
        {
            flag = 1;
            book[tx][ty] = 1;
            step++;
            dfs(tx, ty);
        }
    }
    if(!flag)    return;
    
}
int main(){
    
        idx = -1;
        cin >> n >> m;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                cin >> a[i][j];
        
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)    
                if(!book[i][j])
                {
                    step=1;
                    book[i][j] = 1;
                    dfs(i, j);
                    res[++idx] = step;
                }
                    
        sort(res, res+idx+1);
        for(int i = idx; i >= 0; i --)cout << res[i]<< ' ';
        puts("");
    
    return 0;
}

总结

不是很难，但是代码改了很久，有理解题意的问题，还有板子细节部分忘了

1. 比如样例9到14去，只需判断9东边是否可通即可，14不用管

2. n和m搞反了

3. 主函数中，每次进入dfs，初始(i,j)未标记