题意:题目给出一个n和一幅N*N的图,图中包含'.','X'两种字符,要求在上面放上碉堡,碉堡能攻击他所在的行和列,但不能攻击墙,求最多能放多少个碉堡.
开始每放一个,就把那一位置所在的行列标记,直到遇到墙或边界停止.
这种方法很笨,但由于数据量小,也能AC.
View Code 1 #include2 using namespace std; 3 const int MAX = 5; 4 char map[MAX][MAX]; 5 int used[MAX][MAX]; 6 int n; 7 int max1; 8 void DFS(int rank) 9 { 10 int i,j; 11 int mark = 0; 12 for(i=1;i<=n;i++) 13 { 14 for(j=1;j<=n;j++) 15 { 16 if(used[i][j] == 0 && map[i][j] != 'X') 17 { 18 mark = 1; 19 break; 20 } 21 } 22 if(mark) 23 { 24 break; 25 } 26 } 27 28 29 if(mark == 0) 30 { 31 if(max1 < rank) 32 { 33 max1 = rank; 34 } 35 return ; 36 } 37 for(i=1;i<=n;i++) 38 { 39 for(j=1;j<=n;j++) 40 { 41 if(map[i][j] != 'X' && used[i][j] == 0) 42 { 43 int k; 44 45 for(k=j;k<=n;k++) 46 { 47 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 48 { 49 used[i][k]++; 50 } 51 else 52 { 53 break; 54 } 55 } 56 for(k=j;k>=1;k--) 57 { 58 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 59 { 60 used[i][k]++; 61 } 62 else 63 { 64 break; 65 } 66 } 67 for(k=i;k<=n;k++) 68 { 69 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X') 70 { 71 used[k][j]++; 72 } 73 else 74 { 75 break; 76 } 77 } 78 for(k=i;k>=1;k--) 79 { 80 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X') 81 { 82 used[k][j]++; 83 } 84 else 85 { 86 break; 87 } 88 } 89 90 91 DFS(rank+1); 92 93 94 for(k=j;k<=n;k++) 95 { 96 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 97 { 98 used[i][k]--; 99 }100 else101 {102 break;103 }104 }105 for(k=j;k>=1;k--)106 {107 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X')108 {109 used[i][k]--;110 111 }112 else113 {114 break;115 }116 }117 for(k=i;k<=n;k++)118 {119 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X')120 {121 used[k][j]--;122 123 }124 else125 {126 break;127 }128 }129 for(k=i;k>=1;k--)130 {131 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X')132 {133 used[k][j]--;134 135 }136 else137 {138 break;139 }140 }141 }142 }143 }144 return ;145 }146 int main()147 {148 while(cin>>n,n)149 {150 memset(map,0,sizeof(map));151 memset(used,0,sizeof(used));152 int i,j;153 for(i=1;i<=n;i++)154 {155 for(j=1;j<=n;j++)156 {157 cin>>map[i][j];158 }159 }160 max1 = 0;161 DFS(0);162 cout< <
重新写了代码,改变思路.
把用过的位置标记为' @ '(记住还原) 然后递归,下一次遍历时向四个方向遍历(遍历一行或者一列),若找到'@' 则标记为 不行 若找到'X'或者边界则标记为 行
View Code 1 #include2 using namespace std; 3 const int MAX = 6; 4 int point[4][2] = {-1,0,0,-1,1,0,0,1}; 5 int n; 6 char map[MAX][MAX]; 7 int max1; 8 int judge(int mid_x,int mid_y) 9 {10 int i;11 int mark = 1;12 for(i=0;i<4;i++)13 {14 int x,y;15 x = mid_x;16 y = mid_y;17 while(1)18 {19 x = x + point[i][0];20 y = y + point[i][1];21 if( map[x][y] == '@')22 {23 mark = 0;24 break;25 }26 else27 {28 if(map[x][y] == 'X')29 {30 break;31 }32 else33 {34 if(x<1 || y<1 || x>n || y>n)35 {36 break;37 }38 }39 }40 }41 }42 return mark;43 }44 45 void DFS(int rank)46 {47 int i,j;48 for(i=1;i<=n;i++)49 {50 for(j=1;j<=n;j++)51 {52 if(map[i][j] == '.' && judge(i,j))53 {54 map[i][j] = '@';55 DFS(rank+1);56 map[i][j] = '.';57 }58 }59 }60 if(max1 < rank)61 {62 max1 = rank;63 }64 return ;65 }66 int main()67 {68 while(cin>>n,n)69 {70 memset(map,0,sizeof(map));71 int i,j;72 for(i=1;i<=n;i++)73 {74 for(j=1;j<=n;j++)75 {76 cin>>map[i][j];77 }78 }79 max1 = 0;80 DFS(0);81 cout< <
不过题目好像有问题,附加两个坑爹代码
超时代码
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 const int MAX = 5; 6 char map[MAX][MAX]; 7 int used[MAX][MAX]; 8 int point[4][2] = { 0,1,0,-1,1,0,-1,0}; 9 struct Node 10 { 11 int x; 12 int y; 13 }; 14 int n; 15 int NUM; 16 int num[1100]; 17 int mark2222[10000][10000]; 18 void DFS(int rank) 19 { 20 int i,j; 21 int mark = 0; 22 for(i=1;i<=n;i++) 23 { 24 for(j=1;j<=n;j++) 25 { 26 if(used[i][j] == 0 && map[i][j] != 'X') 27 { 28 mark = 1; 29 break; 30 } 31 } 32 if(mark) 33 { 34 break; 35 } 36 } 37 38 39 if(mark == 0) 40 { 41 num[NUM++] = rank; 42 return ; 43 } 44 45 46 for(i=1;i<=n;i++) 47 { 48 for(j=1;j<=n;j++) 49 { 50 if(map[i][j] != 'X' && used[i][j] == 0) 51 { 52 int k; 53 54 for(k=j;k<=n;k++) 55 { 56 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 57 { 58 used[i][k]++; 59 } 60 else 61 { 62 break; 63 } 64 } 65 for(k=j;k>=1;k--) 66 { 67 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 68 { 69 used[i][k]++; 70 } 71 else 72 { 73 break; 74 } 75 } 76 for(k=i;k<=n;k++) 77 { 78 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X') 79 { 80 used[k][j]++; 81 } 82 else 83 { 84 break; 85 } 86 } 87 for(k=i;k>=1;k--) 88 { 89 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X') 90 { 91 used[k][j]++; 92 } 93 else 94 { 95 break; 96 } 97 } 98 99 100 DFS(rank+1);101 102 103 for(k=j;k<=n;k++)104 {105 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X')106 {107 used[i][k]--;108 }109 else110 {111 break;112 }113 }114 for(k=j;k>=1;k--)115 {116 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X')117 {118 used[i][k]--;119 120 }121 else122 {123 break;124 }125 }126 for(k=i;k<=n;k++)127 {128 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X')129 {130 used[k][j]--;131 132 }133 else134 {135 break;136 }137 }138 for(k=i;k>=1;k--)139 {140 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X')141 {142 used[k][j]--;143 144 }145 else146 {147 break;148 }149 }150 }151 }152 }153 return ;154 }155 int main()156 {157 while(cin>>n,n)158 {159 memset(map,0,sizeof(map));160 memset(used,0,sizeof(used));161 memset(num,0,sizeof(num));162 NUM = 0;163 int i,j;164 for(i=1;i<=n;i++)165 {166 for(j=1;j<=n;j++)167 {168 cin>>map[i][j];169 }170 }171 DFS(0);172 int max = 0;173 for(i=0;i
加了一个二维数组声明 int mark2222[10000][10000]; 成了AC代码
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 const int MAX = 5; 6 char map[MAX][MAX]; 7 int used[MAX][MAX]; 8 int point[4][2] = { 0,1,0,-1,1,0,-1,0}; 9 struct Node 10 { 11 int x; 12 int y; 13 }; 14 int n; 15 int NUM; 16 int num[1100]; 17 int mark2222[10000][10000];//只有这里不同。。。。。。。。。。。。。。。。。。。。。。。 18 void DFS(int rank) 19 { 20 int i,j; 21 int mark = 0; 22 for(i=1;i<=n;i++) 23 { 24 for(j=1;j<=n;j++) 25 { 26 if(used[i][j] == 0 && map[i][j] != 'X') 27 { 28 mark = 1; 29 break; 30 } 31 } 32 if(mark) 33 { 34 break; 35 } 36 } 37 38 39 if(mark == 0) 40 { 41 num[NUM++] = rank; 42 return ; 43 } 44 45 46 for(i=1;i<=n;i++) 47 { 48 for(j=1;j<=n;j++) 49 { 50 if(map[i][j] != 'X' && used[i][j] == 0) 51 { 52 int k; 53 54 for(k=j;k<=n;k++) 55 { 56 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 57 { 58 used[i][k]++; 59 } 60 else 61 { 62 break; 63 } 64 } 65 for(k=j;k>=1;k--) 66 { 67 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X') 68 { 69 used[i][k]++; 70 } 71 else 72 { 73 break; 74 } 75 } 76 for(k=i;k<=n;k++) 77 { 78 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X') 79 { 80 used[k][j]++; 81 } 82 else 83 { 84 break; 85 } 86 } 87 for(k=i;k>=1;k--) 88 { 89 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X') 90 { 91 used[k][j]++; 92 } 93 else 94 { 95 break; 96 } 97 } 98 99 100 DFS(rank+1);101 102 103 for(k=j;k<=n;k++)104 {105 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X')106 {107 used[i][k]--;108 }109 else110 {111 break;112 }113 }114 for(k=j;k>=1;k--)115 {116 if(i>=1 && k>=1 && i<=n && k<=n && map[i][k] != 'X')117 {118 used[i][k]--;119 120 }121 else122 {123 break;124 }125 }126 for(k=i;k<=n;k++)127 {128 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X')129 {130 used[k][j]--;131 132 }133 else134 {135 break;136 }137 }138 for(k=i;k>=1;k--)139 {140 if(i>=1 && k>=1 && i<=n && k<=n && map[k][j] != 'X')141 {142 used[k][j]--;143 144 }145 else146 {147 break;148 }149 }150 }151 }152 }153 return ;154 }155 int main()156 {157 while(cin>>n,n)158 {159 memset(map,0,sizeof(map));160 memset(used,0,sizeof(used));161 memset(num,0,sizeof(num));162 NUM = 0;163 int i,j;164 for(i=1;i<=n;i++)165 {166 for(j=1;j<=n;j++)167 {168 cin>>map[i][j];169 }170 }171 DFS(0);172 int max = 0;173 for(i=0;i
明显是杭电数据有问题。。。