> #include<iostream>
> #include<cstdio>
> #include<algorithm>
> #include<cstring>
> #include<queue>
> using namespace std;
> struct node 
> {
> 	int x,y,sta;
> 	node(int a,int b,int c): x(a),y(b),sta(c) {}
> };
> int n,m,endx,endy;
> char a[510][510];
> int book[510][510][3];
> const int nxtx[3][4]={{-2,0,1,0},{-1,0,1,0},{-1,0,2,0}};
> const int nxty[3][4]={{0,-2,0,1},{0,-1,0,2},{0,-1,0,1}};
> const int nxtz[3][4]={{2,1,2,1},{1,0,1,0},{0,2,0,2}};
> bool in(int x,int y) {return x>=1 && x<=n && y>=1 && y<=m;} 
> bool check(node s)
> {
> 	int x=s.x,y=s.y,sta=s.sta;
> 	if(a[x][y]=='#') return false;
> 	if(!in(x,y)) return false;
> 	if(~book[x][y][sta]) return false;
> 	if(sta==0)
> 	{
> 		if(a[x][y]=='E') return false;
> 		return true;
> 	}
> 	if(sta==1)
> 	{
> 		if(a[x][y+1]=='#') return false;
> 		if(!in(x,y+1)) return false;
> 		return true;
> 	}
> 	if(sta==2)
> 	{
> 		if(a[x+1][y]=='#') return false;
> 		if(!in(x+1,y)) return false;
> 		return true;
> 	}
> 	return true;
> }
> int bfs(int stx,int sty,int ststa)
> {
> 	queue<node> que;
> 	que.push(node(stx,sty,ststa));
> 	book[stx][sty][ststa]=0;
> 	while(!que.empty())
> 	{
> 		node head=que.front(); que.pop();
> 		int x=head.x,y=head.y,sta=head.sta;
> 		int stp=book[x][y][sta]+1;
> 		for(int i=0;i<4;i++)
> 		{
> 			int tx=x+nxtx[sta][i];
> 			int ty=y+nxty[sta][i];
> 			int tsta=nxtz[sta][i];
> 			if(!check(node(tx,ty,tsta))) continue;
> 			book[tx][ty][tsta]=stp;
> 			que.push(node(tx,ty,tsta));
> 			if(tx==endx && ty==endy && tsta==0) return book[tx][ty][tsta];
> 		}
> 	}
> 	return -1;
> }
> // 0/1/2 竖/橫躺/竖躺 
> int main()
> {
> 	while(~scanf("%d %d",&n,&m) && n)
> 	{
> 		endx=endy=0;
> 		memset(a,0,sizeof(a));
> 		memset(book,-1,sizeof(book));
> 		for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
> 		int ststa=0,stx=0,sty=0;
> 		for(int i=1;i<=n;i++)
> 		{
> 			for(int j=1;j<=m;j++)
> 			{
> 				if(a[i][j]=='X') 
> 				{
> 					a[i][j]='.';
> 					stx=i;
> 					sty=j;
> 					if(a[i+1][j]=='X') 
> 					{
> 						ststa=2;
> 						a[i+1][j]='.';
> 					} 
> 					else if(a[i][j+1]=='X') 
> 					{
> 						ststa=1;
> 						a[i][j+1]='.'; 
> 					}
> 					else ststa=0;
> //					break;
> 				} 
> 				if(a[i][j]=='O')
> 				{
> 					endx=i;
> 					endy=j;
> 					a[i][j]='.';
> 				}
> 			}
> 		}
> 		int kkksc03=bfs(stx,sty,ststa);
> 		if(kkksc03!=-1) printf("%d\n",kkksc03);
> 		else puts("Impossible");
> 	}
> 	return 0;
> }

• Re:做了一天的题，留念一下。。 (3) focuschan 2020-03-21 20:52:18