問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1164思路:
其實這題經過分析之后就是一道深度優先搜索題，1次AC...o(∩_∩)o...哈哈
涉及到如何解析一個整數來確定方向的問題，我的解決辦法如下:
1 #define WEST 1
2 #define NORTH 2
3 #define EAST 4
4 #define SOUTH 8
5 #define CAN_GO(sum, dir) (((15-(sum))&dir) != 0)
6 int dir[] = {WEST, NORTH, EAST, SOUTH};
7 int dx[] = {0, -1, 0, 1};
8 int dy[] = {-1, 0, 1, 0};
具體代碼(與PKU 1562類似):
1 void
2 solve()
3 {
4 int i, j, temp;
5 for(i=0; i<row; i++)
6 for(j=0; j<col; j++)
7 if(!visited[i][j]) {
8 total += 1;
9 temp = dfs(i, j);
10 largest = temp > largest ? temp : largest;
11 }
12 }
13
14 int
15 dfs(int i, int j)
16 {
17 int k, sum, rooms = 1;
18 visited[i][j] = 1;
19 sum = castle[i][j];
20 for(k=0; k<4; k++) {
21 if(CAN_GO(sum, dir[k]) && is_valid(i+dx[k], j+dy[k]) && !visited[i+dx[k]][j+dy[k]]) {
22 rooms += dfs(i+dx[k], j+dy[k]); /* 注意這里如何求解room個數 */
23 }
24 }
25 return rooms;
26 }