多测不清空，爆零两行泪。。。。我死了QWQ
每个节点3个状态：横坐标，纵坐标，和方向
说一下方向：0:立着，1:竖着躺着，上半部分在(x,y)，2:横着躺着，左半部分在(x,y)
然后就有了常量数组：
const int dx[3][4]={{-2,0,1,0},{-1,0,2,0},{-1,0,1,0}}; const int dy[3][4]={{0,-2,0,1},{0,-1,0,1},{0,-1,0,2}}; const int dz[3][4]={{1,2,1,2},{0,1,0,1},{2,0,2,0}};
第一维是状态中的方向，第二维是要扩展的方向（0，1，2，3）
然后就搜他。。。。记得queue要清零，d要清零，sz要清零。。。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define R register int const int dx[3][4]={{-2,0,1,0},{-1,0,2,0},{-1,0,1,0}}; const int dy[3][4]={{0,-2,0,1},{0,-1,0,1},{0,-1,0,2}}; const int dz[3][4]={{1,2,1,2},{0,1,0,1},{2,0,2,0}}; using namespace std; inline int g() { R ret=0; register char ch; while(!isdigit(ch=getchar())); do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret; } struct node{ int x,y,z; node() {} node(int xx,int yy,int zz):x(xx),y(yy),z(zz) {} }; queue<node>q; char e[510][510]; int n,m,sx,sy,sz,ex,ey; int d[510][510][3]; inline bool ckpos(int x,int y) {return x>0&&x<=n&&y>0&&y<=m;} inline bool ck(int x,int y,int z) { if(!ckpos(x,y)||e[x][y]=='#'||d[x][y][z]!=-1) return false; if(z==0&&e[x][y]=='E') return false; if(z==1&&(!ckpos(x+1,y)||e[x+1][y]=='#')) return false; if(z==2&&(!ckpos(x,y+1)||e[x][y+1]=='#')) return false; return true; } int bfs() { memset(d,-1,sizeof(d)); while(q.size()) q.pop(); q.push(node(sx,sy,sz)); d[sx][sy][sz]=0; while(q.size()) { node u=q.front(); q.pop(); for(R i=0;i<4;++i) { node v=node(u.x+dx[u.z][i],u.y+dy[u.z][i],dz[u.z][i]); //cout<<u.x<<" "<<u.y<<" "<<u.z<<" "<<v.x<<" "<<v.y<<" "<<v.z<<endl; if(!ck(v.x,v.y,v.z)) continue; q.push(v),d[v.x][v.y][v.z]=d[u.x][u.y][u.z]+1; if(v.x==ex&&v.y==ey&&v.z==0) return d[v.x][v.y][v.z]; } } return -1; } signed main() { while(n=g(),m=g(),n!=0) { sz=0; for(R i=1;i<=n;++i) scanf("%s",e[i]+1); for(R i=1;i<=n;++i) for(R j=1;j<=m;++j) if(e[i][j]=='X') { sx=i,sy=j; e[i][j]='.'; if(j<m&&e[i][j+1]=='X') sz=2,e[i][j+1]='.'; if(i<n&&e[i+1][j]=='X') sz=1,e[i+1][j]='.'; } else if(e[i][j]=='O') ex=i,ey=j,e[i][j]='.'; R ans=bfs(); ans==-1?printf("Impossible "):printf("%d ",ans); //for(R i=1;i<=n;++i,cout<<' ') for(R j=1;j<=m;++j) cout<<d[i][j][0]<<" "<<d[i][j][1]<<" "<<d[i][j][2]<<" "; } }
2019.04.26