P7012 tj

· · 题解

传送门

第六篇题解，如有不妥请忽视指出。

题目大意：

给定一个国际跳棋棋盘，你现在是白方，该你走棋，求你最多可以吃多少颗棋子。

算法：

搜索。

解析：

这道题大体思路应该好想，但有一些小细节需要注意。

先几句话把大体思路讲一下。很容易想到，它可能会有多颗白棋，那么每一颗棋子都要搜一遍，看一下最多能吃多少颗棋子，最终再看吃的最多的那颗棋子吃了多少颗。

然后就是一些小细节：

  1. 搜索时注意每一步都要还原，而且不是只还原 1 个，码量有点多（有点抽象，看下面的代码）。

  2. 多组数据，不清零见祖宗！！！

  3. 我栽在这一个点上。清零就够了，不要给习惯性地他设成负的多少，因为题目中说：如果没有合法的棋步（例如，棋盘上没有白棋），只需输出 0。没搜到时，由于最大值初始化为 0，所以输出时直接输出就行了。

好了，该说的也说完了，那我放代码了。放代码之前，祝大家新年快乐（尽管春节已经过了几天了……）！

Code:

#include<bits/stdc++.h>
using namespace std;
long long n,mmax,dx[]={-2,-2,2,2},dy[]={-2,2,2,-2};     //祝大家新的一年里龙（long）腾虎跃！
char a[15][15];
void dfs(long long x,long long y,long long cnt)
{
    if((a[x-1][y-1]!='B' || a[x-2][y-2]!='#') && (a[x-1][y+1]!='B' || a[x-2][y+2]!='#') && (a[x+1][y-1]!='B' || a[x+2][y-2]!='#') && (a[x+1][y+1]!='B' || a[x+2][y+2]!='#'))    //判断条件，有点长，但还好理解
    {
        mmax=max(mmax,cnt);
        return; 
    }
    for(int i=0;i<4;i++)
    {
        long long nx=x+dx[i],ny=y+dy[i];
        if(nx>0 && nx<11 && ny>0 && ny<11 && a[nx][ny]!='B' && a[nx][ny]!='W')
        {
            if(i==0 && a[x-1][y-1]=='B')
            {
                a[x-1][y-1]='#';
                a[x][y]='#';
                a[nx][ny]='W';
                dfs(nx,ny,cnt+1);
                a[x-1][y-1]='B';
                a[x][y]='W';
                a[nx][ny]='#';          //要还原 3 个格子，所以这里的代码比较长
            }
            if(i==1 && a[x-1][y+1]=='B')
            {
                a[x-1][y+1]='#';
                a[x][y]='#';
                a[nx][ny]='W';
                dfs(nx,ny,cnt+1);
                a[x-1][y+1]='B';
                a[x][y]='W';
                a[nx][ny]='#';
            }
            if(i==2 && a[x+1][y+1]=='B')
            {
                a[x+1][y+1]='#';
                a[x][y]='#';
                a[nx][ny]='W';
                dfs(nx,ny,cnt+1);
                a[x+1][y+1]='B';
                a[x][y]='W';
                a[nx][ny]='#';
            }
            if(i==3 && a[x+1][y-1]=='B')
            {
                a[x+1][y-1]='#';
                a[x][y]='#';
                a[nx][ny]='W';
                dfs(nx,ny,cnt+1);
                a[x+1][y-1]='B';
                a[x][y]='W';
                a[nx][ny]='#';
            }
        }
    }
}
int main()
{
    scanf("%lld",&n);
    while(n--)
    {
        for(int i=1;i<11;i++)
        {
            for(int j=1;j<11;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=1;i<11;i++)
        {
            for(int j=1;j<11;j++)
            {
                if(a[i][j]=='W')
                {
                    dfs(i,j,0);
                }
            }
        }
        printf("%lld\n",mmax);
        mmax=0;                     //要清零，而且设为0就够了
    }
    return 0;
}

注：代码已 AC 过，请放心食用。

最后，浏览过看过也要赞过！