hdu 4499 Cannon dfs

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4499

题意:

在一个象棋棋盘上放炮，要求两个炮不能互相打到，然后问你最多能放几个炮

题解:

dfs 一直dfs到最后一行最后一列就可以每个点只往上和往左扫了
vis[x][y]= 0 表示这个点没有棋子 1表示普通的棋子 2表示炮

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 int n,m,q,ans,vis[6][6];
18 
19 void dfs(int x,int y, int cnt){ //一行一行地搜索，直到找到最后一行时结束时记录最大值
20     if(x >= n){ 
21         ans = max(ans,cnt);
22         return ;
23     }
24     if(y >= m){
25         dfs(x+1,0,cnt);
26         return ;
27     }
28 
29     if(vis[x][y]){
30         dfs(x,y+1,cnt);
31         return ;
32     }
33 
34     dfs(x,y+1,cnt);
35 
36     int t;
37     for(t=y-1; t>=0; t--){
38         if(vis[x][t]) break;
39     }
40     int f = 0;
41     for(int i=t-1; i>=0; i--){
42         if(vis[x][i]==2) { f = 1; break;}
43         if(vis[x][i]) break;
44     }
45     if(f) return ; //判断这一列上是否存在炮互吃
46     f = 0;
47     for(t=x-1; t>=0; t--){
48         if(vis[t][y]) break;
49     }
50     for(int i=t-1; i>=0; i--){
51         if(vis[i][y] == 2) { f=1; break;}
52         if(vis[i][y]) break;
53     }
54     if(f) return ; //判断这一行上是否存在炮互吃
55     vis[x][y] = 2;
56     dfs(x,y+1,cnt+1);
57     vis[x][y] = 0; //回溯
58 }
59 
60 int main(){
61     while(scanf("%d%d%d",&n,&m,&q)!=EOF){
62         ans = 0;
63         memset(vis,0,sizeof(vis));
64         for(int i=1; i<=q; i++){
65             int x=read(),y=read();
66             vis[x][y] = 1;
67         }
68 
69         dfs(0,0,0);
70         cout << ans << endl;
71     }
72 
73     return 0;
74 }