原创的思维和代码永远比看题解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;
}