题意 : 给你一张图上面" X " 代表墙 , " . " 代表空地 , 让你在空地上放置炮台 , 条件是 不能 让彼此的炮台 可以互相看见 ( 隔着墙就看不见了 ) , 问你最多可以放置 多少个炮台 .
题解 : 二话不说上去直接暴力搜索 , 给的图最大不超过 5 * 5 所以 就直接暴力 了 , 但是 八皇后那里以前写过一个 0ms 的代码 , 一会去看看 , 一段时间不看就忘了 , 一会附上优化代码 . 还有就是 这个将两个for循环写成一个for循环 真的特别简单 而且还不容易出错 ...
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #include<iostream>
5 #include<algorithm>
6 #include<queue>
7 #include<vector>
8 #include<set>
9 #include<stack>
10 #include<string>
11 #include<sstream>
12 #include<map>
13 #include<cctype>
14 using namespace std; //有点类似于 八皇后问题
15 char a[5][5]; //图 不大 可以暴力一点
16 int visited[5][5],maxn,n1,result;
17 bool check(int x,int y,int n)
18 {
19 for(int i=x-1;i>=0&&a[y][i]!='X';i--)
20 if(a[y][i]=='@')
21 return false;
22 for(int i=x+1;i<n&&a[y][i]!='X';i++)
23 if(a[y][i]=='@')
24 return false;
25 for(int i=y-1;i>=0&&a[i][x]!='X';i--)
26 if(a[i][x]=='@')
27 return false;
28 for(int i=y+1;i<n&&a[i][x]!='X';i++)
29 if(a[i][x]=='@')
30 return false;
31 return true;
32 }
33 void DFS(int x,int n)
34 {
35 for(int i=x;i<n1;i++)
36 {
37 int i1=i/n,j1=i%n;
38 if(a[i1][j1]!='X'&&!visited[i1][j1]&&check(j1,i1,n))
39 {
40 visited[i1][j1]=1;
41 a[i1][j1]='@';
42 maxn++;
43 result=maxn>result?maxn:result;
44 DFS((j1+1)*(i1+1),n);
45 maxn--;
46 a[i1][j1]='.';
47 visited[i1][j1]=0;
48 }
49 }
50 }
51 int main()
52 {
53 int n;
54 while(scanf("%d",&n),n)
55 {
56 n1=n*n;
57 for(int i=0;i<n1;i++)
58 {
59 int i1=i/n,j1=i%n;
60 scanf(" %c",&a[i1][j1]);
61 }
62 result=maxn=0;
63 memset(visited,0,sizeof(visited));
64 DFS(0,n);
65 printf("%d
",result);
66 }
67 return 0;
68 }