本文共 1851 字，大约阅读时间需要 6 分钟。
#include #include #include #include #include #include #include #include #include #include #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const double eps = 1e-14; const int inf = 0x3f3f3f3f; const double pi=acos(-1); using namespace std; char f[30][30]; int sx,sy,tx,ty; int step[30][30][6][6],cas=0,n,m; bool visit[30][30][6][6]; struct node{ int x,y,c,d; node(){}; node(int xx,int yy,int cc,int dd):x(xx),y(yy),c(cc),d(dd){} }; node ne[20000]; int dx[5]={ -1,0,1,0};//北东南西 int dy[5]={ 0,1,0,-1}; bool legal(node nt,int dir,int i) { if((dir==0&&i==2)||(dir==1&&i==3)||(dir==2&&i==0)||(dir==3&&i==1)) return false; if(nt.x<0||nt.x>=n||nt.y<0||nt.y>=m) return false; if(f[nt.x][nt.y]=='#') return false; if(visit[nt.x][nt.y][nt.c][nt.d]) return false; return true; } void solve() { printf("Case #%d\n",cas); memset(step,inf,sizeof(step)); memset(visit,false,sizeof(visit)); node S(sx,sy,0,0); queue q; q.push(S); step[S.x][S.y][S.c][S.d]=0; while(q.size()) { node cur=q.front();q.pop(); // printf("%d %d %d %d\n",cur.x,cur.y,cur.c,cur.d); if(cur.x==tx&&cur.y==ty&&cur.c==0) { printf("minimum time = %d sec\n",step[cur.x][cur.y][cur.c][cur.d]); return; } visit[cur.x][cur.y][cur.c][cur.d]=true; int dir=cur.d,color=cur.c; for(int i=0;i<4;i++) { node tp; if(i==dir) tp=(node){ cur.x+dx[i],cur.y+dy[i],(cur.c+1)%5,i}; else tp=(node){ cur.x,cur.y,cur.c,i}; if(!legal(tp,dir,i)) continue; q.push(tp); step[tp.x][tp.y][tp.c][tp.d]=step[cur.x][cur.y][cur.c][cur.d]+1; } } printf("destination not reachable\n"); } int main() { while(~scanf("%d %d",&n,&m)) { if(!n&&!m) return 0; ++cas; for(int i=0;i
转载地址：http://qtgsi.baihongyu.com/