城堡问题
题目 城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
方向：上北下南左西右东。
图1是一个城堡的地形图。
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 m*n个方格区域，每个方格区域可以有0~4面墙。
注意：墙体厚度忽略不计。
输入格式
第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。
接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。
每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。
例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。
输入的数据保证城堡至少有两个房间。
输出格式
共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
数据范围
输入样例：
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
输出样例：
5
9
思路分析
每个方格可以被看作是图中的一个节点，方格中的墙表示节点间是否有边相连（即是否可以直接从一个方格到达另一个方格）
1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和（1西 10北 100东 1000南）可以用位运算来判断墙的存在。如果一个方格的值为3（即二进制的11），那么我们知道这个方格有西墙（位1）和北墙（位2）。因此，我们可以用g[i][j] & 1来判断西墙是否存在，用g[i][j] & 2来判断北墙是否存在，以此类推
结合枚举4个方向就可以写成 if (g[x][y] >> i & 1) continue;
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=60;
int g[N][N];
bool st[N][N];
int size;
int n,m;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m && !st[x][y];//这里从1开始
}
void dfs(int x,int y){
for(int i=0;i<4;i++){
if(g[x][y]>>i&1)//四个方向是否有墙
continue;
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny)){
size++;
st[nx][ny]=true;
dfs(nx,ny);
//只能用一次 不能回溯
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
int ans=0,res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!st[i][j]){
size=0;
dfs(i,j);
ans++;
res=max(res,size);
}
}
}
cout<<ans<<endl<<res<<endl;
return 0;
}
bfs写法
#include <iostream>
#include <queue>
using namespace std;
typedef pair <int,int> PII;
const int N = 60;
int dx[] = {0,-1,0,1},dy[] = {-1,0,1,0};
int n,m,ans = 0,res = 0;
int g[N][N];
bool vis[N][N];
int bfs (int i,int j) {
queue <PII> q;
q.push ({i,j});
vis[i][j] = true;
int cnt = 0;
while (!q.empty ()) {
PII t = q.front ();
q.pop ();
cnt++;
for (int k = 0;k < 4;k++) {
if (g[t.first][t.second] >> k & 1) continue;
int x = t.first + dx[k],y = t.second + dy[k];
if (vis[x][y]) continue;
q.push ({x,y});
vis[x][y] = true;
}
}
return cnt;
}
int main () {
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) cin >> g[i][j];
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
if (!vis[i][j]) {
ans++;
res = max (res,bfs (i,j));
}
}
}
cout << ans << endl << res << endl;
return 0;
}
同类题型
视频讲解
⬅️ Lake Counting S 🏠 00-刷题理模型 ➡️ 山峰和山谷
💬 评论