| 记录编号 |
598681 |
评测结果 |
AAAAAAAA |
| 题目名称 |
城堡 |
最终得分 |
100 |
| 用户昵称 |
 LikableP |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.028 s |
| 提交时间 |
2025-02-16 10:55:38 |
内存使用 |
3.38 MiB |
显示代码纯文本
/*
ID: likable1
TASK: castle
LANG: C++11
*/
//这是一个 C++ 程序，目的是打破一面蓝色的墙
#include <iostream> //这是一个头文件，cin cout 都在里面
#include <fstream> //这是一个头文件，用于文件输出
#include <queue> //这是一个头文件，用于队列的操作
using namespace std; //使用 std 命名空间
//空行使我的代码更美观
int m, n; //城堡大小
int maxx = -1, maxi, maxj, maxd; //打破一面墙后可获得的最大房间大小，打破的墙的坐标，打破的墙的方向
int a[60][60]; //城堡数据
bool walls[60][60][5]; // wall[i][j] 表示 (i,j) 是否有墙，第三维表示方向， 1 2 3 4 分别表示西 北 东 南 四个方向是否有墙
int roomIdx[60][60]; // roomIdx[i][j] 表示 (i,j) 属于第几号房间
bool vis[60][60]; //标记数组
int roomSize[7200]; // roomSize[i] 表示第 i 号房间的大小
int roomCount; //房间数量
int maxSize; //最大房间大小
queue <int> qx, qy; //两个队列用于 bfs
//空行使我的代码更美观
int dx[] = {0, 0, -1, 0, 1}; // x 坐标偏移量 注意按照 左 上 右 下 的顺序存
int dy[] = {0, -1, 0, 1, 0}; // y 坐标偏移量 注意按照 左 上 右 下 的顺序存
//空行使我的代码更美观
void bfs(int x, int y) { //宽度优先搜索，传递两个参数 x,y 分别表示搜索起点的 x 坐标和 y 坐标
vis[x][y] = true; //先将起点标记，防止重复走起点
roomCount++; //房间总数增加，先增加以保证房间号从 1 开始
qx.push(x); //将当前点入队
qy.push(y);
while (!qx.empty()) { //一直搜索知道队列为空，即没有一个点未被标记且属于当前房间
int nx = qx.front(); //获取队首的坐标
int ny = qy.front();
roomIdx[nx][ny] = roomCount; //将队首坐标的房间号设为当前房间总数
roomSize[roomCount]++; //将当前房间的大小加 1
maxSize = max(maxSize, roomSize[roomCount]); //更新最大房间大小
for (int i = 1; i <= 4; i++) { //遍历四个方向
int cx = nx + dx[i]; //先求出下一步的坐标
int cy = ny + dy[i];
if (cx >= 1 && cx <= n && cy >= 1 && cy <= m && !vis[cx][cy] && !walls[nx][ny][i]) { //判断下一个坐标能不能走，及判断下一步坐标是否越界/是否走过以及俩房间中间有没有墙，这就体现了 walls 以及 dx dy 变量按照 左上右下 顺序存储的好处
vis[cx][cy] = true; //标记下一步的坐标，防止重复走一个房间
qx.push(cx); //将下一步坐标入队
qy.push(cy);
}
}
qx.pop(); //记得弹出队首元素，否则会死循环
qy.pop();
}
}
//空行使我的代码更美观
int isEdge(int x, int y) { //isEdge 函数用于求出当前房间在哪些方向与**其他**房间相连，并返回一个整型，返回的数字是由以下四个整数的某个或某几个或一个都没有加起来的。1: 与西面的房间之间有墙 2: 与北面的房间之间有墙 4: 与东面的房间之间有墙 8: 与南面的房间之间有墙，但注意如果当前房间在边界的话，边界的方向不能算到里面
int res = 0; //定义返回的数，初始化为零
for (int i = 1; i <= 4; i++) { //遍历四个方向
int cx = x + dx[i]; //求出四个方向房间的坐标
int cy = y + dy[i];
if (roomIdx[cx][cy] != roomIdx[x][y] && roomIdx[cx][cy]) { //判断新方向是否是**另一个房间**并且排除边界的情况
res |= (0x1 << (i - 1)); //巧用位运算，当 i 分别等于 1 2 3 4 时会将 res 分别增加 1 2 4 8
}
}
return res; //返回结果
}
//空行使我的代码更美观
int main() { //这是主函数，程序从这里开始运行
freopen("castle.in", "r", stdin); //打开 castle.in 文件并重定向标准输入
freopen("castle.out", "w", stdout); //打开 castle.out 文件并重定向标准输出
cin >> m >> n; //读入城堡的大小
for (int i = 1; i <= n; i++) { //遍历整个城堡
for (int j = 1; j <= m; j++) {
cin >> a[i][j]; //读入房间 (i,j) 墙的数据
//开始解码，位运算很好用哒
if (a[i][j] >> 0 & 0x1) walls[i][j][1] = true; //左
if (a[i][j] >> 1 & 0x1) walls[i][j][2] = true; //上
if (a[i][j] >> 2 & 0x1) walls[i][j][3] = true; //右
if (a[i][j] >> 3 & 0x1) walls[i][j][4] = true; //下
}
}
//空行使我的代码更美观
for (int i = 1; i <= n; i++) { //遍历整个城堡的所有房间
for (int j = 1; j <= m; j++) {
if (!roomIdx[i][j]) { //如果当前房间没有搜过，即没有房间号
bfs(i, j); //则开始宽搜
}
}
}
//空行使我的代码更美观
for (int j = 1; j <= n; j++) { //遍历整个城堡的所有房间
for (int i = n; i >= 1; i--) { //注意从左下角开始遍历到右上角，一列一列遍历
int edge = isEdge(i, j); //获取当前房间与其他房间相连的情况
if (edge) { //如果与其他房间有相连
for (int d = 1; d <= 4; d++) { //遍历四个方向
if (edge & (0x1 << (d - 1))) { //如果解码后是 1 的话，则说明该房间与方向 d 右其他房间相连
int cx = i + dx[d]; //那么求出那个房间的坐标
int cy = j + dy[d];
if (roomSize[roomIdx[cx][cy]] + roomSize[roomIdx[i][j]] > maxx) { //如果这两个房间大小之和大于 maxx 的话
maxx = roomSize[roomIdx[cx][cy]] + roomSize[roomIdx[i][j]]; //更新 maxx 值
maxi = i; //更新坐标
maxj = j;
maxd = d; //更新方向
}
}
}
}
}
} //好多缩进，好多大括号 qwq
//空行使我的代码更美观
cout << roomCount << endl; //输出房间数量
cout << maxSize << endl; //输出最大房间的大小
cout << maxx << endl; //输出拆掉一面墙后和获得的最大房间的大小
cout << maxi << ' ' << maxj << ' '; //输出拆掉墙的坐标
switch (maxd) { //输出拆掉墙的方向
case 1:
cout << 'W';
break;
case 2:
cout << 'N';
break;
case 3:
cout << 'E';
break;
case 4:
cout << 'S';
break;
}
cout << endl;
return 0; //记得加 return 0 哦呐呐
}