BZOJ 4761

2019-11-10 22:05:52

字體：大中小

來源：轉載

供稿：網友

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]);