一开始以为瞎jb写个IDA*就过了。。然而并不是这样。(naive)
我的做法是dp[x1][y1][x2][y2][d1][d2]，表示两头奶牛所在的位置和面朝的方向，然后直接spfa搞定。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 25 using namespace std; int n,map[maxn][maxn],dis[maxn][maxn][maxn][maxn][5][5]; char s[maxn]; int dx[]={0,-1,0,1,0},dy[]={0,0,1,0,-1}; bool vis[maxn][maxn][maxn][maxn][5][5]; struct status { int x1,x2,y1,y2,d1,d2; status (int x1,int y1,int x2,int y2,int d1,int d2):x1(x1),y1(y1),x2(x2),y2(y2),d1(d1),d2(d2) {} status () {} }; queue <status> q; bool judge(int x,int y) { return ((x>=1) && (x<=n) && (y>=1) && (y<=n)); } void spfa() { q.push(status(n,1,n,1,1,2)); while (!q.empty()) { status head=q.front();q.pop(); int nx1,nx2,ny1,ny2; nx1=head.x1+dx[head.d1];nx2=head.x2+dx[head.d2];ny1=head.y1+dy[head.d1];ny2=head.y2+dy[head.d2]; int t2=dis[head.x1][head.y1][head.x2][head.y2][head.d1][head.d2]; if ((!judge(nx1,ny1)) || (!map[nx1][ny1])) nx1=head.x1,ny1=head.y1; if ((!judge(nx2,ny2)) || (!map[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) { t1=t2+1; bool &t3=vis[nx1][ny1][nx2][ny2][head.d1][head.d2]; if (!t3) { t3=true; q.push(status(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; int &t5=dis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]; if (t5>t2+1) { t5=t2+1; bool &t3=vis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]; if (!t3) { t3=true; q.push(status(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; int &t4=dis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]; if (t4>t2+1) { t4=t2+1; bool &t3=vis[head.x1][head.y1][head.x2][head.y2][dd1][dd2]; if (!t3) { t3=true; q.push(status(head.x1,head.y1,head.x2,head.y2,dd1,dd2)); } } } } int main() { 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 mn=0x3f3f3f3f; for (int i=1;i<=4;i++) for (int j=1;j<=4;j++) mn=min(mn,dis[1][n][1][n][i][j]); printf("%d ",mn); return 0; }