首页 > 代码库 > poj 1164 The Castle
poj 1164 The Castle
题目链接：
http://poj.org/problem?id=1164
题目描述：
有一个n*m的castle，有一个个小房间组成，每个房间由一个零和四面的墙组成，每个房间都有一个价值，
价值的计算方式是：west_walls价值为1，north_walls价值为2，east_walls价值为4，south_walls价值为8，
walls的价值加在一起就是这个房间的价值。先输入n，m，随后输入n*m的数字矩阵。问castle有几个房间，最大的房间多大？
解题思路：
利用二进制对每个房间的walls进行状态压缩，然后dfs转化为求连通块问题。（重点在于模型建立）
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 using namespace std; 5 6 #define N 55 7 int map[N][N], num, sum, n, m; 8 int dir[][2] = {0,-1, -1,0, 0,1, 1,0}; 9 10 void dfs (int x, int y);11 12 int main ()13 {14 int i, j, max;15 while (scanf ("%d %d", &n, &m) != EOF)16 {17 for (i=0; i<n; i++)18 for (j=0; j<m; j++)19 scanf ("%d", &map[i][j]);20 num = max = 0;21 for (i=0; i<n; i++)22 for (j=0; j<m; j++)23 if (map[i][j] != -1)24 {25 sum = 0;26 dfs (i, j);27 num ++;28 if (max < sum)29 max = sum;30 }31 printf ("%d\n%d\n", num, max);32 }33 return 0;34 }35 36 void dfs (int x, int y)37 {38 int s = map[x][y];39 sum ++;40 map[x][y] = -1;41 for (int i=0; i<4; i++)42 {43 if (s % 2 == 0)44 {45 int a = x + dir[i][0];46 int b = y + dir[i][1];47 if (a>=0 && a<n && b<m && b>=0 && map[a][b] != -1)48 dfs(a, b);49 }50 s /= 2;51 }52 53 }
poj 1164 The Castle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。