hdu 1045

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1045

题意：给定一个最大4*4的方形地图，里面有墙(X)和空地(.)。在每个空地上可以放大炮，但两个大炮如果在同一行或同一列并且之间没有墙阻隔的话，会互相攻击，所以不能同时存在。问最多能放多少个大炮。

mark：数据小，直接dfs就可以了。1WA，把保存状态的数组开成了全局的- -。据说还可以二分匹配过。

代码：

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 
 5 char g[4][4] ;
 6 int vis[4][4] ;
 7 int n, ans ;
 8 int tab[4][2] = {0,1,0,-1,1,0,-1,0} ;
 9 
10 
11 void dfs(int pos, int num)
12 {
13     int x = pos/n, y = pos%n ;
14     int xx, yy, i, j ;
15     int buff[4][4] ;
16 //    if(pos==n*n) return ;
17     if (g[x][y]=='X')return ;
18     if (vis[x][y]==1) return ;
19 
20     for(i=0;i<n;i++)for(j=0;j<n;j++)buff[i][j]=vis[i][j];
21     vis[x][y]=1;
22     for(i=0;i<4;i++)
23     {
24         for(xx=x+tab[i][0],yy=y+tab[i][1] ;
25             xx>=0&&xx<n&&yy>=0&&yy<n&&g[xx][yy]=='.';
26             xx+=tab[i][0],yy+=tab[i][1])
27             vis[xx][yy]=1 ;
28     }
29     if(num+1>ans)ans=num+1;
30     for(i=pos+1;i<n*n;i++)dfs(i,num+1);
31     for(i=0;i<n;i++)for(j=0;j<n;j++)vis[i][j]=buff[i][j];
32 }
33 
34 
35 int main ()
36 {
37     int i ;
38     while (~scanf("%d",&n)&&n)
39     {
40         for(i=0;i<n;i++) scanf("%s",g[i]) ;
41         memset(vis,0,sizeof(vis)) ;
42         ans=0;
43         for(i=0;i<n*n;i++)dfs(i,0) ;
44         printf("%d\n", ans) ;
45     }
46     return 0 ;
47 }