【杭电acm】1045 Fire Net
经典深搜。注意满足条件。
1 #include <stdio.h> 2 #include <string.h> 3 4 #define MAXNUM 5 5 6 char map[MAXNUM][MAXNUM]; 7 int visit[MAXNUM][MAXNUM]; 8 9 int chk(int row, int col, int n) { 10 int i, k; 11 12 if (row<0 || row>=n || col<0 || col>=n ) 13 return 0; 14 if (visit[row][col] || map[row][col]!=‘.‘) 15 return 0; 16 17 // if this position is valid or not 18 k = 0; 19 for (i=col-1; i>=0; --i) { 20 if (map[row][i] == ‘X‘) 21 break; 22 if (map[row][i] == ‘.‘ && visit[row][i]) { 23 k = 1; 24 break; 25 } 26 } 27 if (k) return 0; 28 29 for (i=col+1; i<n; ++i) { 30 if (map[row][i] == ‘X‘) 31 break; 32 if (map[row][i] == ‘.‘ && visit[row][i]) { 33 k = 1; 34 break; 35 } 36 } 37 if (k) return 0; 38 39 for (i=row-1; i>=0; --i) { 40 if (map[i][col] == ‘X‘) 41 break; 42 if (map[i][col] == ‘.‘ && visit[i][col]) { 43 k = 1; 44 break; 45 } 46 } 47 if (k) return 0; 48 49 for (i=row+1; i<n; ++i) { 50 if (map[i][col] == ‘X‘) 51 break; 52 if (map[i][col] == ‘.‘ && visit[i][col]) { 53 k = 1; 54 break; 55 } 56 } 57 58 if (k) 59 return 0; 60 else 61 return 1; 62 } 63 64 int dfs(int n) { 65 int i, j, tmp, max = 0; 66 67 for (i=0; i<n; ++i) { 68 for (j=0; j<n; ++j) { 69 if ( chk(i, j, n) ) { 70 visit[i][j] = 1; 71 tmp = dfs(n) + 1; 72 if (tmp > max) 73 max = tmp; 74 visit[i][j] = 0; 75 } 76 } 77 } 78 79 return max; 80 } 81 82 int main() { 83 int n, amount; 84 int i; 85 86 while (scanf("%d", &n)!=EOF && n) { 87 getchar(); 88 for (i=0; i<n; ++i) 89 gets(map[i]); 90 91 memset(visit, 0, sizeof(visit)); 92 amount = dfs(n); 93 printf("%d\n", amount); 94 } 95 96 return 0; 97 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。