原创的思维和代码永远比看题解A的兴奋的多！
原创的思维和代码永远比看题解A的兴奋的多！！
原创的思维和代码永远比看题解A的兴奋的多！！！
原创的思维和代码永远比看题解A的兴奋的多！！！！
原创的思维和代码永远比看题解A的兴奋的多！！！！！
原创的思维和代码永远比看题解A的兴奋的多！！！！！！
哪怕算法效率上差别人很多
昨天的周常比赛我看到这题就知道用暴力回溯 想想应该和八皇后难度上差不了多少 就放到最后一小时再写 结果就懵逼了
越写越乱 最后也没写出来 晚上也一直在想 结果发现 越深究，我的思路漏洞越多，这个问题也变得越来越有趣，今天早上还是被我A了 真是痛快
思路就是暴力回溯 具体的 见注释（其实我不建议你看我代码，因为我觉得太臭了，但毕竟是自己亲生的，哈哈哈哈哈哈哈哈哈哈
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int ans,row,col;
int mat[10][10];//整个棋盘我分为4种状态 0 空 1 其他棋子 2 放炮排斥位置 3 炮
void update(int x,int y)
{
bool flag=true;
for(int i=y+1; i<col-1&&flag; i++)//对坐标右行进行更新
if(mat[x][i]==1&&mat[x][i+1]==1) break;//遇到两个相邻的其他棋子就不需要了
else if(mat[x][i]==1)//如果只是一个其他棋子
for(int j=i+1; j<col; j++)
if(mat[x][j]==1){flag=false;break;}//再碰到一个其他棋子
else mat[x][j]=2;
for(int i=0; i<y; i++)//对坐标坐标进行更新
if(mat[x][i]==3&&mat[x][i+1]!=1&&mat[x][i+2]!=1)//如果前面有炮并且没有两个相邻的其他棋子阻隔 (其实这里还写不大好，抄了小路，既然A了就算了
for(int j=y+1; j<col; j++)
if(mat[x][j]==1) break;//碰到一个其他棋子
else mat[x][j]=2;
flag=true;
for(int i=x+1; i<row-1&&flag; i++)
if(mat[i][y]==1&&mat[i+1][y]==1) break;
else if(mat[i][y]==1)
for(int j=i+1; j<row; j++)
if(mat[j][y]==1) {flag=false;break;}
else mat[j][y]=2;
for(int i=0; i<x; i++)
if(mat[i][y]==3&&mat[i+1][y]!=1&&mat[i+2][y]!=1)
for(int j=x+1; j<row; j++)
if(mat[j][y]==1) break;
else mat[j][y]=2;
}
void dfs(int r,int num,int add,int st)
{
if(r==row)
{
ans=max(num,ans);
return ;
}
int temprow[7],tempcol[7],tt;
for(int i=st; i<col; i++)
{
if(mat[r][i]==0)
{
for(int j=0; j<col; j++)
temprow[j]=mat[r][j];
for(int j=0; j<row; j++)
tempcol[j]=mat[j][i];
tt=mat[r][i];//最傻最暴力的备份方法
mat[r][i]=3;//放炮
update(r,i);//更新
if(add<2&&i<col-1) dfs(r,num+1,add+1,i+1); //对于一行来说 最多可以放3个炮 同行递归
dfs(r+1,num+1,0,0);//同行递归不行就下一行
mat[r][i]=tt;//还原
for(int j=0; j<col; j++)
mat[r][j]=temprow[j];
for(int j=0; j<row; j++)
mat[j][i]=tempcol[j];
}
}
dfs(r+1,num,0,0);//也有可能我一正行都不能放反而更优
}
int main()
{
int num,x,y;
while(scanf("%d%d%d",&row,&col,&num)!=EOF)
{
memset(mat,0,sizeof mat);
for(int i=0; i<num; i++)
{
scanf("%d%d",&x,&y);
mat[x][y]=1;
}
ans=0;
dfs(0,0,0,0);
printf("%d\n",ans);
}
return 0;
}