自动搬运

查看原文

来自洛谷，原作者为

	荣一鸣 **

搬运于2025-08-24 21:31:10，当前版本为作者最后更新于2018-11-04 17:03:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题是一道十分奇怪的dp题

首先，我们要对于这道题目做出一点抗议，那就是在一开始，机器人是面对着上方的

为了常试出这一点我交了好几次。。。

好吧，开始正题

很明显，我们可以记录当机器人在这个时间走到了$(i,j)$这个点并且面对的方向是$k$的时候的最小拒绝次数

即，用$dp[i][j][k][l]$来存走$l$次到这里的最小拒绝次数

然后就可以分类状态转移了，很显然在该点要么是这一次拒绝了，要么是从另一个状态转移过来

首先是$LEFT$

在我这里0~3分别表示右，下，左，上

那么$LEFT$的转移方程就是

$dp[i][j][k][l]=min(dp[i][j][k][l-1]+1,dp[i][j][(k+1)$%$4][l-1])$

同理科的$RIGHT$得方程

然后就是$BACK$

$dp[i][j][k][l]=min(dp[i][j][k][l-1]+1,dp[i+dx[k]][j+dx[k]][k][l-1])$

$FORWORD$同$BACK$

然后就是代码

#include<bits/stdc++.h>
#define y0 kjdskjfkdsj
using namespace std;
int n,m,x0,y0,dp[110][110][4][2];
char mp[110][110],s[10];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

char readchar(){
	char c=getchar();
	while(c!='.'&&c!='*') c=getchar();
	return c;
}

int main(){
	scanf("%d%d%d%d",&m,&n,&x0,&y0);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			mp[i][j]=readchar();
	memset(dp,0x3f,sizeof(dp));dp[x0][y0][3][0]=0;
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		switch(s[0]){
			case 'L':{
				for(int j=1;j<=m;j++)
					for(int k=1;k<=m;k++)
						for(int l=0;l<=3;l++)
							dp[j][k][l][i%2]=min(dp[j][k][l][(i%2)^1]+1,dp[j][k][(l+1)%4][(i%2)^1]);
				break;
			}
			case 'R':{
				for(int j=1;j<=m;j++)
					for(int k=1;k<=m;k++)
						for(int l=0;l<=3;l++)
							dp[j][k][l][i%2]=min(dp[j][k][l][(i%2)^1]+1,dp[j][k][(l+3)%4][(i%2)^1]);
				break;
			}
			case 'F':{
				for(int j=1;j<=m;j++)
					for(int k=1;k<=m;k++)
						for(int l=0;l<=3;l++)
							dp[j][k][l][i%2]=min(dp[j][k][l][(i%2)^1]+1,dp[j-dx[l]][k-dy[l]][l][(i%2)^1]);
				for(int j=1;j<=m;j++)
					for(int k=1;k<=m;k++)
						if(mp[j][k]=='*')
							for(int l=0;l<=3;l++)
								dp[j][k][l][i%2]=0x3f3f3f3f;
				break;
			}
			case 'B':{
				for(int j=1;j<=m;j++)
					for(int k=1;k<=m;k++)
						for(int l=0;l<=3;l++)
							dp[j][k][l][i%2]=min(dp[j][k][l][(i%2)^1]+1,dp[j+dx[l]][k+dy[l]][l][(i%2)^1]);
				for(int j=1;j<=m;j++)
					for(int k=1;k<=m;k++)
						if(mp[j][k]=='*')
							for(int l=0;l<=3;l++)
								dp[j][k][l][i%2]=0x3f3f3f3f;
				break;
			}
		}
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			for(int l=0;l<=3;l++)
				ans=min(ans,dp[i][j][l][n%2]);
	printf("%d",ans);
}