dp[i][j][k][[l]: 执行第i步，执行到点（j，k），方向为l时，用的最大步数。
状态转移根据step[i]转移。
#include&stdio.h&
#include&string.h&
#include&algorithm&
#include&iostream&
#define INF
int xx[4]={1,0,-1,0};
int yy[4]={0,-1,0,1};
int dp[2][111][111][4];
int step[1100];
int map[110][110];
int main()
int n,m,x0,y0,i,j,k,l;
char str[10001];
while(~scanf(&%d%d%d%d&,&n,&m,&x0,&y0))
for(i=1;i&=n;i++)
scanf(&%s&,str);
for(j=1;j&=n;j++)
if(str[j-1]=='*')map[i][j]=0;
else map[i][j]=1;
for(i=1;i&=m;i++)
scanf(&%s&,str);
strcmp(str,&FORWARD&)==0)step[i]=1;
else if( strcmp(str,&BACK&)==0)step[i]=2;
else if( strcmp(str,&LEFT&)==0)step[i]=3;
else if(strcmp(str,&RIGHT&)==0)step[i]=4;
for(i=0;i&2;i++)
for(j=0;j&=n+10;j++)
for(k=0;k&=n+10;k++)
for(l=0;l&4;l++)dp[i][j][k][l]=-INF;
dp[0][x0][y0][0]=0;
for(i=1;i&=m;i++)
for(j=1;j&=n;j++)
for(k=1;k&=n;k++)
if(map[j][k]==0)
for(l=0;l&4;l++)
if(step[i]==1)
dp[i%2][j][k][l]=max(dp[(i+1)%2][j+xx[l]][k+yy[l]][l]+1,dp[(i+1)%2][j][k][l]);
else if(step[i]==2)
dp[i%2][j][k][l]=max(dp[(i+1)%2][j-xx[l]][k-yy[l]][l]+1,dp[(i+1)%2][j][k][l]);
else if(step[i]==3)
dp[i%2][j][k][l]=max(dp[(i+1)%2][j][k][(l+4-1)%4]
+1,dp[(i+1)%2][j][k][l]);
else if(step[i]==4)
dp[i%2][j][k][l]=max(dp[(i+1)%2][j][k][(l+1)%4]
+1,dp[(i+1)%2][j][k][l]);
maxn=max(maxn,dp[i%2][j][k][l]);
cout&&m-maxn&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：439244次
积分：9361
积分：9361
排名：第1352名
原创：499篇
评论：123条
(3)(3)(1)(6)(1)(4)(14)(14)(33)(29)(25)(25)(22)(11)(12)(26)(28)(17)(18)(5)(4)(17)(6)(18)(8)(34)(7)(9)(5)(3)(21)(33)(12)(18)(10)(5)