hdu 4499 Cannon（DFS）

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

（看到標題第一反應...不是“炮”是，以為是佳能= =買照相機去了...）

本題大意是給你一個N*M的棋盤

然後給你Q個坐標，這些坐標上都是有棋子的。

接著放象棋裡的“炮”...炮的規則大家都懂得吧，就是目標子與“炮”本身之間有且只有一個棋子時，炮可以吃掉目標子

問你最多可以放幾個炮，使得“炮”之間不會互相攻擊（攻擊已有棋子不算）

DFS的一道題目，用回溯法，其實就是8皇後的升級版呗~

題目是個5*5的棋盤，直接暴力棋盤+深搜就行，感覺其實不剪枝也行，不過我還是剪了點

我是從上到下，從左到有逐行放置“炮的”

代碼如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m,q,x,y,sum;
int chess[6][6];
void dfs(int x,int y,int cnt)
{
    bool flag=true;
    if(x>=n)
    {
        sum=max(cnt,sum);
        return ;
    }
    if(y>=m)//列到頭就重新另起一行
    {
        dfs(x+1,0,cnt);
        return ;
    }
    if(chess[x][y]==1)
    {
        dfs(x,y+1,cnt);
        return ;
    }
    dfs(x,y+1,cnt);
    int i;
    for(i=x-1;i>=0;i--)
    {
        if(chess[i][y])
        {
            break;
        }
    }
    for(int j=i-1;j>=0;j--)
    {
        if(chess[j][y])
        {
            if(chess[j][y]==2)
                flag=false;
            break;
        }
    }
    if(!flag)
        return ;
    for(i=y-1;i>=0;i--)
    {
        if(chess[x][i])
        {
            break;
        }
    }
    for(int j=i-1;j>=0;j--)
    {
        if(chess[x][j])
        {
            if(chess[x][j]==2)
                flag=false;
            break;
        }
    }
    if(!flag)
        return ;
    chess[x][y]=2;
    dfs(x,y+1,cnt+1);
    chess[x][y]=0;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&q)!=EOF)
    {
        memset(chess,0,sizeof chess);
        sum=0;
        while(q--)
        {
            scanf("%d%d",&x,&y);
            chess[x][y]=1;
        }
        dfs(0,0,0);
        printf("%d\n",sum);
    }
    return 0;
}