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
%d
", 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 }

本文为博主原创文章，未经博主允许不得转载。