HDU 4499 Cannon （暴力搜索）

题意：在n*m的方格里有t个棋子，问最多能放多少个炮且每一个炮不能互相攻击（炮吃炮）

炮吃炮：在同一行或同一列且中间有一颗棋子。

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <queue>

#include <math.h>

#define M 50

#define LL long long

using namespace std;

using  namespace  std;

int n,m,t,ans;

int ma[M][M];

bool bfs(int x,int y)//推断x，y能不能放

{

	int xx=x-1;

	int cnt=0;

	while(xx>=0)

	{

		if(ma[xx][y]==1&&cnt==1) return false;

		if(ma[xx][y]==1||ma[xx][y]) cnt++;

		xx--;

	}

	xx=x+1;

	cnt=0;

	while(xx<n)

	{

		if(ma[xx][y]==1&&cnt==1) return false;

		if(ma[xx][y]==1||ma[xx][y]) cnt++;

		xx++;

	}

	int yy=y-1;

	cnt=0;

	while(yy>=0)

	{

		if(ma[x][yy]==1&&cnt==1) return false;

		if(ma[x][yy]==1||ma[x][yy]) cnt++;

		yy--;

	}

	yy=y+1;

	cnt=0;

	while(yy<m)

	{

		if(ma[x][yy]==1&&cnt==1) return false;

		if(ma[x][yy]==1||ma[x][yy]) cnt++;

		yy++;

	}

	return true;

}

void dfs(int x,int y,int tmp)

{

	if(tmp>ans) ans=tmp;

	for(int i=x;i<n;i++)

	{

		for(int j=0;j<m;j++)

		{

			if(i==x&&j<y) continue;

			if(ma[i][j]!=-1&&bfs(i,j))

			{

				ma[i][j]=1;

				dfs(i,j+1,tmp+1);

				ma[i][j]=0;

			}

		}

	}

}

int main()

{

	  while(~scanf("%d%d%d",&n,&m,&t))

	  {

        memset(ma,0,sizeof(ma));

        int  x,y;

        while (t--)

		{

            scanf( "%d %d" ,&x,&y);

            ma[x][y]=-1;

        }

        ans=0;

        dfs(0,0,0);

        printf("%d\n",ans);

    }

}