問題:
http://poj.org/problem?id=1154思路:
教科書式的DFS，一次AC
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 21
5 #define is_valid(x, y) (x>=0&&x<R&&y>=0&&y<C)
6 const int dx[] = {-1, 1, 0, 0};
7 const int dy[] = {0, 0, -1, 1};
8 int R, C;
9 int rt, hash[26]; /* A-Z */
10 char map[MAX_LEN][MAX_LEN];
11
12 void
13 dfs(int x, int y, int cur)
14 {
15 int i, mark, next_x, next_y;
16 mark = 0;
17 hash[map[x][y]] = 1;
18 for(i=0; i<4; i++) {
19 next_x = x + dx[i];
20 next_y = y + dy[i];
21 if(is_valid(next_x, next_y) && !hash[map[next_x][next_y]]) {
22 mark = 1;
23 hash[map[next_x][next_y]] = 1;
24 dfs(next_x, next_y, cur+1);
25 hash[map[next_x][next_y]] = 0;
26 }
27 }
28 if(!mark)
29 rt = cur>rt ? cur : rt;
30 }
31
32 int
33 main(int argc, char **argv)
34 {
35 int i;
36 while(scanf("%d %d", &R, &C) != EOF) {
37 for(i=0; i<R; i++)
38 scanf("%s", map[i]);
39 rt = -1;
40 memset(hash, 0, sizeof(hash));
41 dfs(0, 0, 1);
42 printf("%d\n", rt);
43 }
44 }