题解 P1859 【不听话的机器人】

· · 题解

本题是一道十分奇怪的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);
}