自动搬运

查看原文

来自洛谷，原作者为

	lyh0217 qwq

搬运于2025-08-24 22:50:56，当前版本为作者最后更新于2023-10-06 11:12:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

由于 $n$，$m$，$k$，都 $\leq6$，而 $T$ 也$\leq 20$，可以直接暴力搜索。

每一次寻找一个当前存在棋子的格子，往上，下，左，右四个方向，判断合不合法，判断条件为题面中的图，若合法，就按题意走出一步，并继续搜索。

还有，注意回溯和处理边界！

时间复杂度为 $O(T \times 4^k)$，可以通过此题。

AC code:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
bool vis[15][15];
void dfs(int p)
{
	ans=min(ans,p);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(vis[i][j])
			{
				if(j>=3&&vis[i][j-1]&&!vis[i][j-2])//往左跳
				{
					vis[i][j-1]=0;
					vis[i][j]=0;
					vis[i][j-2]=1;
					dfs(p-1);
					vis[i][j-1]=1;
					vis[i][j]=1;
					vis[i][j-2]=0;
				}
				if(i>=3&&vis[i-1][j]&&!vis[i-2][j])//往上跳
				{
					vis[i-1][j]=0;
					vis[i][j]=0;
					vis[i-2][j]=1;
					dfs(p-1);
					vis[i-1][j]=1;
					vis[i][j]=1;
					vis[i-2][j]=0;
				}
				if(j<=m-2&&vis[i][j+1]&&!vis[i][j+2])//往右跳
				{
					vis[i][j+1]=0;
					vis[i][j]=0;
					vis[i][j+2]=1;
					dfs(p-1);
					vis[i][j+1]=1;
					vis[i][j]=1;
					vis[i][j+2]=0;
				}
				if(i<=n-2&&vis[i+1][j]&&!vis[i+2][j])//往下跳
				{
					vis[i+1][j]=0;
					vis[i][j]=0;
					vis[i+2][j]=1;
					dfs(p-1);
					vis[i+1][j]=1;
					vis[i][j]=1;
					vis[i+2][j]=0;
				}
			}
		}
	}
}
int main(){
	int t;
	cin>>t;
	while(t--)
	{
		memset(vis,0,sizeof(vis));  //多测不清空，爆零两行泪
		ans=6;          //因为最多有六个棋子，所以初始化为六即可
		cin>>n>>m>>k;
		for(int i=1;i<=k;i++)
		{
        int x,y;
			cin>>x>>y;
			vis[x][y]=1;  //标记在此位置有一个棋子
		}
		dfs(k);
		cout<<ans<<endl;
	}
	return 0;
}

评测记录