请问这道“城堡问题”如何理解呢?请帮注释一下,谢谢
#include <stack>
#include <cstring>
using namespace std;
#define MAXN 60
int R,C;
int rooms[MAXN][MAXN];
int color[MAXN][MAXN];
int maxRoomArea = 0;
int colorNum = 0;
int roomArea;
void Dfs(int i, int k) {
if(___color[i][k] ___) {
return;
}
++roomArea;
color[i][k] = colorNum;
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]) {
____++colorNum ________;
roomArea = 0;
Dfs(i, k);
maxRoomArea = max(roomsArea, maxRoomArea);
}
}
}
cout << colorNum << endl;
cout << maxRoomArea << endl;
return 0;
}
添加注释过程中,发现无法编译通过,修改了一部分无法通过编译的内容;
有一些循环的开始和结束位置发现是有问题的,顺手也修改了,希望我修改后的程序还是你原来的意图
#include <stack>
#include <cstring>
#include <iostream>
using namespace std;
#define MAXN 60
int R, C;
int rooms[MAXN][MAXN];
int color[MAXN][MAXN];
int maxRoomArea = 0;
int colorNum = 0;
int roomArea;
void Dfs(int i, int k) {
if (i < 0 || k < 0 || i >= R || k >= C)//检查i,k的有效性
{
return;
}
if (color[i][k]) {//已设置颜色(颜色不为0),则直接返回
return;
}
++roomArea;//增加房间区域计数
color[i][k] = colorNum;//设置当前区域颜色编号
//房间类型分别为1,2,4,8,每个房间可以包含四种类型
//1类房间,直接跳转到左侧房间设置
//1类房间,和左侧房间是同色的
if ((rooms[i][k] & 1) == 0) {
Dfs(i, k - 1);
}
//2类房间,直接跳转到上侧房间设置
//2类房间,和上侧房间是同色的
if ((rooms[i][k] & 2) == 0) {
Dfs(i - 1, k);
}
//4类房间,直接跳转到右侧房间设置
//4类房间,和右侧房间是同色的
if ((rooms[i][k] & 4) == 0) {
Dfs(i, k + 1);
}
//8类房间,直接跳转到下侧房间设置
//8类房间,和下侧房间是同色的
if ((rooms[i][k] & 8) == 0) {
Dfs(i + 1, k);
}
}
int main() {
//输入房间大小尺寸,R表示竖向大小,C表示左右大小
cin >> R >> C;
//输入每个房间类型
for (int i = 0; i < R; i++)
{
for (int k = 0; k < C; k++) {
cin >> rooms[i][k];
}
}
//清空color数组
memset(color, 0, sizeof(color));
//遍历
for (int i = 0; i < R; i++) {
for (int k = 0; k < C; k++) {
if (!color[i][k]) {//未设置颜色
//颜色编号增加
++colorNum;
//房间区域初始化为0
roomArea = 0;
//
Dfs(i, k);
//计算最大的房间区域数
maxRoomArea = max(roomArea, maxRoomArea);
}
}
}
cout << colorNum << endl;//打印使用的颜色数量(或最后使用的颜色编号)
cout << maxRoomArea << endl;//最大的房间区域数
return 0;
}