【简单dfs】Bubble Cup 14 传送门 Problem - 1600J - Codeforces 题目 题意 题解 AC代码 总结 不是很难,但是代码改了很久,有理解题意的问题,还有板子细节部分忘了
题目 
题意
给定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)未标记