自动搬运

查看原文

来自洛谷，原作者为

	SevenElevenThirteen Steppenwolf.

搬运于2025-08-24 21:41:02，当前版本为作者最后更新于2020-07-02 21:13:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P2739 [USACO4.4]棋盘游戏Shuttle Puzzle题解

这是一道可以练习搜索的好题，我采用的是dfs和剪枝优化。

观察样例，发现白子只往右走、黑子只往左走，那么搜索总共也就四种情况：白子挪一格、白子跳一格、黑子挪一格、黑子跳一格。（注意只能跳过一个不同颜色的棋子）

剪枝也很好想，记录最少所用的步数，如果当前步数已经比它大了，就直接返回，避免因多次递归而超时。

奉上AC代码$\;$通过记录

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int n,a[10005],b[10005],sum = 2147483647;
string now = " ",tar = " ";//now是当前状态，tar是目标状态
void dfs(int step,int pos)//step是已用步数，pos是空格位置
{
	if (step >= sum)//剪枝
		return ;
	if (now == tar)//更新答案
	{
		sum = step;
		for (int i = 1;i <= step;i++)
		{
			a[i] = b[i];
		}
		return ;
	}
	if (pos - 2 > 0 && now[pos - 2] == 'W' && now[pos - 1] == 'B')//白子跳一格 
	{
		b[step + 1] = pos - 2;
		now[pos - 2] = ' ';
		now[pos] = 'W';
		dfs(step + 1,pos - 2);
		b[step + 1] = 0;//回溯
		now[pos - 2] = 'W';
		now[pos] = ' ';
	}
	if (pos - 1 > 0 && now[pos - 1] == 'W')//白子挪一格 
	{
		b[step + 1] = pos - 1;
		now[pos - 1] = ' ';
		now[pos] = 'W';
		dfs(step + 1,pos - 1);
		b[step + 1] = 0;
		now[pos - 1] = 'W';
		now[pos] = ' ';
	}
	if (pos + 1 <= n * 2 + 1 && now[pos + 1] == 'B')//黑子挪一格 
	{
		b[step + 1] = pos + 1;
		now[pos + 1] = ' ';
		now[pos] = 'B';
		dfs(step + 1,pos + 1);
		b[step + 1] = 0;
		now[pos + 1] = 'B';
		now[pos] = ' ';
	}
	if (pos + 2 <= n * 2 + 1 && now[pos + 2] == 'B' && now[pos + 1] == 'W')//黑子跳一格 
	{
		b[step + 1] = pos + 2;
		now[pos + 2] = ' ';
		now[pos] = 'B';
		dfs(step + 1,pos + 2);
		b[step + 1] = 0;
		now[pos + 2] = 'B';
		now[pos] = ' ';
	}
	return ;
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)//产生初始状态与目标状态
	{
		now += 'W';
		tar += 'B';
	}
	now += ' ';
	tar += ' ';
	for (int i = 1;i <= n;i++)
	{
		now += 'B';
		tar += 'W';
	}
	dfs(0,n + 1);
	for (int i = 1;i <= sum;i++)
	{
		cout << a[i] << " ";
		if (i % 20 == 0)//每行20个数
			cout << endl;
	}
	cout << endl;
    return 0;
}

点个赞再走吧！