自动搬运

查看原文

来自洛谷，原作者为

	David_yang 没有一根棒棒糖解决不了的事情，如果有，就再来一根

搬运于2025-08-24 22:25:52，当前版本为作者最后更新于2024-02-22 20:20:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

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

题目大意：

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

算法：

搜索。

解析：

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

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

然后就是一些小细节：

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 过，请放心食用。

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