2019 深信服下棋（DFS+回溯）

链接：https://www.nowcoder.com/questionTerminal/a0feb0696e2043a5b3b0779fa861b64a?f=discussion
来源：牛客网

8x8的棋盘上，布有黑白两色棋子，白子先下，当白子下N手后，棋盘上最多有可能留下多少颗白子？

下法规则：
1.每次落子后，以该棋子为中心的8个方向(米字形的8条直线)，如果有同色棋子，
且两个同色棋子之间连续排列着若干个异色棋子，无空白及同色棋子。则，这次落子可以把这些夹在中间的异色棋子全部翻色（即黑变白，白变黑）。

2. 黑白子交错落子。

3. 如果一个位置上有棋子，不能继续在该位置上落子；

4. 如果一个位置上落子后，不能翻对手的棋子，则该位置不能落子；

1表示黑色，2表示白色，0表示空白未落子
白棋落子后，棋盘变化情况如下所示：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 => 0 0 0 1 2 0 0 0
0 0 0 2 1 0 0 0 0 0 0 2 2 2 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 => 0 0 0 1 2 0 0 0
0 0 1 2 1 2 0 0 0 0 1 2 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输入描述:

第一行为白子需要走的步数

接下来8行数据，指明棋盘上的棋子状态，其中1为黑子，2为白子，0为空位置

输出描述:

白子下完N手后，棋盘上的白子个数的最大可能。

示例1

输入

1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0
0 0 0 2 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

输出

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;
typedef pair<int,int> p;


int mp[8][8];
int dir[8][2]={-1,0,1,0,0,-1,0,1,-1,-1,-1,1,1,-1,1,1};//上，下，左，右，左上，右上，左下，右下
int n,ans;

int find_sum(int x,int y,int dx,int dy,int nwcolor,int others)
{
    int cnt=1;
    x+=dx; y+=dy;
    while(x>=0&&x<8&&y>=0&&y<8)
    {
        if(mp[x][y]==nwcolor)
            return cnt;
        if(mp[x][y]!=others)
            return 0;
        x+=dx;
        y+=dy;
        cnt++;
    }
    return 0;
}
void dfs(int step)
{
    if(step==n)
    {
        int cnt=0;
        for(int i=0; i<8; i++)
        {
            for(int j=0; j<8; j++)
                if(mp[i][j]==2) cnt++;
        }
        ans=max(ans,cnt);
        return;
    }
    int nw,lst;
    vector<p> g;//保存要改变的棋子位置
    if(step%2==0)
    {
        nw=2;
        lst=1;
    }
    else
    {
        nw=1;
        lst=2;
    }
    for(int i=0; i<8; i++)
    {
        for(int j=0; j<8; j++)
        {
            if(mp[i][j]==0)
            {
                int flag=0;//回溯标记
                for(int k=0; k<8; k++)
                {
                    int cnt=find_sum(i,j,dir[k][0],dir[k][1],nw,lst);//从当前位置[i,j]沿当前方向可以改变多少个棋子
                    if(cnt>1)
                    {
                        int x=i,y=j;
                        for(int ii=0; ii<cnt; ii++)
                        {
                            mp[x][y]=nw;
                            g.push_back(make_pair(x,y));//保存要更新的棋子位置
                            x+=dir[k][0];
                            y+=dir[k][1];
                        }
                        flag=1;
                    }
                }
                if(flag)
                {
                    dfs(step+1);
                    for(int ii=0; ii<g.size(); ii++)//回溯
                    {
                        mp[g[ii].first][g[ii].second]=lst;
                    }
                    mp[i][j]=0;
                    g.clear();
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    n=2*n-1;
    for(int i=0; i<8; i++)
    {
        for(int j=0; j<8; j++)
        {
            scanf("%d",&mp[i][j]);
        }
    }
    ans=0;
    dfs(0);
    printf("%d\n",ans);
    return 0;
}

0