dp+最短路
首先考虑了dfs，但不能处理要求的头朝哪个方向的问题。
然后考虑dp dp[x1][y1][x2][y2][d1][d2]表示第一个人（初始头朝上）在x1,y2位置 头的朝向是d1，第二个人（初始头朝右）在x2,y2位置，头朝向是d2的时候 最少需要多少步
dp就是dis，因为每个状态之间的转移都是单位长度，spfa求最短路就是最少步数。
有几种转移： 1.d1,d2不变，朝着现在方向走一步（不能越界或者是障碍，否则原地，到了目的地也是原题踏步） 2.两个人位置不变，d1,d2改变，绕着圈圈转就好了。。1 2 3 4 1 2。。。这样循环。。
转移求的过程就是spfa辣。。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <queue>const int maxn = 25;using namespace std;int n,map[maxn][maxn],dis[maxn][maxn][maxn][maxn][5][5];char s[maxn];int dir[5][2] = { {0,0},{-1,0},{0,1},{1,0},{0,-1} };bool vis[maxn][maxn][maxn][maxn][5][5];bool judge(int x,int y){ if((x>=1) && (x<=n) && (y>=1) && (y<=n) && map[x][y] == 1) return true; return false;}struct node{ int x1,x2,y1,y2,d1,d2;};queue<node> q;void qin(int a,int b,int c,int d,int e,int f){ node tmp; tmp.x1 = a;tmp.x2 = c;tmp.y1 = b;tmp.y2 = d;tmp.d1 = e;tmp.d2 = f; q.push(tmp);}void spfa(){ qin(n,1,n,1,1,2); while (!q.empty()){ node head=q.front();q.pop(); int nx1,nx2,ny1,ny2; nx1=head.x1+dir[head.d1][0];nx2=head.x2+dir[head.d2][0]; ny1=head.y1+dir[head.d1][1];ny2=head.y2+dir[head.d2][1]; int t2=dis[head.x1][head.y1][head.x2][head.y2][head.d1][head.d2]; if (!judge(nx1,ny1)) nx1=head.x1,ny1=head.y1; if (!judge(nx2,ny2)) nx2=head.x2,ny2=head.y2; if ((head.x1==1) && (head.y1==n)) nx1=1,ny1=n; if ((head.x2==1) && (head.y2==n)) nx2=1,ny2=n; int t1=dis[nx1][ny1][nx2][ny2][head.d1][head.d2]; if (t1>t2+1){ dis[nx1][ny1][nx2][ny2][head.d1][head.d2]=t2+1; if (!vis[nx1][ny1][nx2][ny2][head.d1][head.d2]){ vis[nx1][ny1][nx2][ny2][head.d1][head.d2] = true; qin(nx1,ny1,nx2,ny2,head.d1,head.d2); } } int dd1,dd2; dd1=head.d1-1;dd2=head.d2-1;if (!dd1) dd1=4;if (!dd2) dd2=4; if (dis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]>t2+1){ dis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]=t2+1; if (!vis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]){ vis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]=true; qin(head.x1,head.y1,head.x2,head.y2,dd1,dd2); } } dd1=head.d1+1;dd2=head.d2+1; if (dd1==5) dd1=1;if (dd2==5) dd2=1; if (dis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]>t2+1){ dis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]=t2+1; if (!vis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]){ vis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]=true; qin(head.x1,head.y1,head.x2,head.y2,dd1,dd2); } } }}void init(){ scanf("%d",&n); memset(dis,0x3f,sizeof(dis)); for(int i =1 ; i <= n ; i++){ scanf("%s",s); for (int j = 0;j < n;j++){ if (s[j]=='E') map[i][j+1]=1; } } dis[n][1][n][1][1][2]=0; spfa(); int ans=(1<<30); for (int i = 1;i <= 4;i++) for (int j = 1;j <= 4;j++) ans=min(ans,dis[1][n][1][n][i][j]); PRintf("%d/n",ans);}int main(){ init();}新闻热点
疑难解答
