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[][];

int dir[][]={-,,,,,-,,,-,-,-,,,-,,};//上，下，左，右，左上，右上，左下，右下

int n,ans;

int find_sum(int x,int y,int dx,int dy,int nwcolor,int others)

{

    int cnt=;

    x+=dx; y+=dy;

    while(x>=&&x<&&y>=&&y<)

    {

        if(mp[x][y]==nwcolor)

            return cnt;

        if(mp[x][y]!=others)

            return ;

        x+=dx;

        y+=dy;

        cnt++;

    }

    return ;

}

void dfs(int step)

{

    if(step==n)

    {

        int cnt=;

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

        {

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

                if(mp[i][j]==) cnt++;

        }

        ans=max(ans,cnt);

        return;

    }

    int nw,lst;

    vector<p> g;//保存要改变的棋子位置

    if(step%==)

    {

        nw=;

        lst=;

    }

    else

    {

        nw=;

        lst=;

    }

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

    {

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

        {

            if(mp[i][j]==)

            {

                int flag=;//回溯标记

                for(int k=; k<; k++)

                {

                    int cnt=find_sum(i,j,dir[k][],dir[k][],nw,lst);//从当前位置[i,j]沿当前方向可以改变多少个棋子

                    if(cnt>)

                    {

                        int x=i,y=j;

                        for(int ii=; ii<cnt; ii++)

                        {

                            mp[x][y]=nw;

                            g.push_back(make_pair(x,y));//保存要更新的棋子位置

                            x+=dir[k][];

                            y+=dir[k][];

                        }

                        flag=;

                    }

                }

                if(flag)

                {

                    dfs(step+);

                    for(int ii=; ii<g.size(); ii++)//回溯

                    {

                        mp[g[ii].first][g[ii].second]=lst;

                    }

                    mp[i][j]=;

                    g.clear();

                }

            }

        }

    }

}

int main()

{

    scanf("%d",&n);

    n=*n-;

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

    {

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

        {

            scanf("%d",&mp[i][j]);

        }

    }

    ans=;

    dfs();

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

    return ;

}

棋子