重庆网络问政平台/桂林seo排名

2815:城堡问题
查看 提交 统计 提示 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成mn(m≤50，n≤50)个方块，每个方块可以有0~4面墙。
输入
程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(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
来源
1164

题解：dfs求连通块问题。从一个没有访问过的点出发，dfs此点附近所有可以到达的点，函数返回值是此点周围所有没有被访问过且能到达的点的数目总和。比较各个返回值大小，最大的就是题目要求的最大房间方块数。如果一个连通块求完后没有覆盖所有房间，即仍有房间的vis为0，则重新求连通块，再比较出最大房间方块数。而每重新求连通块的时候都使num++，这样就能算出总共有多少房间。

思考：
1、&是很好用的符号
2、一定要先判断下一步可不可以走再走
3、一定要把行和列搞清楚再往下写

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>using namespace std;
const int maxn = 55;
int room[maxn][maxn], vis[maxn][maxn], maxsiz, num;
int m, n;int dfs(int x, int y)
{vis[x][y] = num;int siz1 = 0;if (x - 1 >= 1 && !vis[x - 1][y] && (room[x][y] & 2) == 0) {siz1 += dfs (x - 1, y);}if (x + 1 <= m && !vis[x + 1][y] && (room[x][y] & 8) == 0) {siz1 += dfs (x + 1, y);}if (y + 1 <= n && !vis[x][y + 1] && (room[x][y] & 4) == 0) {siz1 += dfs (x, y + 1);}if (y - 1 >= 1 && !vis[x][y - 1] && (room[x][y] & 1) == 0) {siz1 += dfs (x, y - 1);}return siz1 + 1;
}int main()
{#ifndef ONLINE_JUDGEfreopen ("in.txt", "r", stdin);#endif // ONLINE_JUDGEscanf ("%d%d", &m, &n);memset (room, 0, sizeof(room));memset (vis, 0, sizeof(vis));maxsiz = 0;num = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {scanf ("%d", &room[i][j]);}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (!vis[i][j]) {num++;int siz = dfs (i, j);if (siz > maxsiz) {maxsiz = siz;}}}}printf ("%d\n%d\n", num, maxsiz);return 0;
}