DFS。
1 /* 2782 */ 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 #define MAXN 650 10 11 int n, m; 12 bool visit[MAXN][MAXN]; 13 int ansd, ansx, ansy, ansb; 14 int dir[4][2] = { 15 // E, N, S, W. 16 0,1, -1,0, 1,0, 0,-1 17 }; 18 int link[4][2] = { 19 1,2, 0,3, 0,3, 1,2 20 }; 21 char op[5] = "ENSW"; 22 23 24 inline bool check(int x, int y) { 25 return x<0 || x>=n || y<0 || y>=m; 26 } 27 28 int dfs(int x, int y, int d) { 29 int i, j, k, tmp; 30 int xx, yy; 31 int ret = 0; 32 33 if (d == -1) { 34 for (i=0; i<4; ++i) { 35 xx = x + dir[i][0]; 36 yy = y + dir[i][1]; 37 if (check(xx, yy) || visit[xx][yy]) 38 continue; 39 k = 0; 40 while (!check(xx, yy) && !visit[xx][yy]) { 41 ++k; 42 visit[xx][yy] = true; 43 xx += dir[i][0]; 44 yy += dir[i][1]; 45 } 46 xx -= dir[i][0]; 47 yy -= dir[i][1]; 48 tmp = k + dfs(xx, yy, i); 49 if (tmp > ansb) { 50 ansb = tmp; 51 ansx = x; 52 ansy = y; 53 ansd = i; 54 } 55 while (k--) { 56 visit[xx][yy] = false; 57 xx -= dir[i][0]; 58 yy -= dir[i][1]; 59 } 60 } 61 } else { 62 for (j=0; j<2; ++j) { 63 i = link[d][j]; 64 xx = x + dir[i][0]; 65 yy = y + dir[i][1]; 66 if (check(xx, yy) || visit[xx][yy]) 67 continue; 68 k = 0; 69 while (!check(xx, yy) && !visit[xx][yy]) { 70 ++k; 71 visit[xx][yy] = true; 72 xx += dir[i][0]; 73 yy += dir[i][1]; 74 } 75 xx -= dir[i][0]; 76 yy -= dir[i][1]; 77 tmp = k + dfs(xx, yy, i); 78 if (tmp > ret) 79 ret = tmp; 80 while (k--) { 81 visit[xx][yy] = false; 82 xx -= dir[i][0]; 83 yy -= dir[i][1]; 84 } 85 } 86 } 87 return ret; 88 } 89 90 int main() { 91 int t = 0; 92 int i, j, k; 93 94 #ifndef ONLINE_JUDGE 95 freopen("data.in", "r", stdin); 96 #endif 97 98 while (scanf("%d %d",&n,&m)!=EOF && (n||m)) { 99 memset(visit, false, sizeof(visit));100 scanf("%d", &k);101 while (k--) {102 scanf("%d %d", &i, &j);103 visit[i][j] = true;104 }105 ansb = -1;106 for (i=0; i