北大oj百练-2815:城堡问题
【北大oj百练-2815:城堡问题】注意点：房间数的++在DFS外，房间大小的++在DFS内部
#include
#include
#include
#define maxn 60
using namespace std;
int R,C;
//R表示行数，C表示列数
int rooms [maxn][maxn];
int color [maxn][maxn];
//方块是否染色过的标记
int maxRoomArea=0,roomNum=0;
int roomArea;
void Dfs(int i, int k) //i表示上下，k表示左右
{
if(color[i][k])
return ;
roomArea++;
color[i][k]=roomNum;
//随便赋一个不为0的数
if((rooms[i][k]&1)==0) Dfs(i,k-1);
//如果西边没墙,向西走
if((rooms[i][k]&2)==0) Dfs(i-1,k);
//向北
if((rooms[i][k]&4)==0) Dfs(i,k+1);
//向东
if((rooms[i][k]&8)==0) Dfs(i+1,k);
//向南
}
int main()
{
cin >> R >> C;
for(int i=1;
i<=R;
i++)
{
for(int k=1;
k<=C;
k++)
{
cin >> rooms[i][k];
}
}
memset(color,0,sizeof(color));
for(int i=1;
i<=R;
i++)
{
for(int k=1;
k<=C;
k++)
{
if(!color[i][k])
{
roomNum++;
roomArea=0;
Dfs(i,k);
maxRoomArea=max(roomArea,maxRoomArea);
}
}
}
cout << roomNum < 推荐阅读
- 期刊|期刊 | 国内核心期刊之（北大核心）
- 临清一中学子斩获北大培文杯作文大赛全国大奖
- 这份史上最经典的3大学习方法，清华北大学霸都在用！
- 《|《 香帅的北大金融学课》问答题
- 2019-12-24|2019-12-24 想读清华北大必须进入全国的前0.03%
- 动态规划——数字三角形（百练ID2760）
- 香帅的北大金融学课:羊群效应（“模仿跟风”是理性行为（））
- 北大博士悔恨（不规划方向|北大博士悔恨：不规划方向 学历越高越失败）
- 刘莐（感受到冷，才能看到风口）
- 【e医疗原创】北大一院周国鹏（说到底，国情决定了发展路径）