#include<iostream>
#include<queue>
#define MAX 550
using namespace std;

struct node
{
	int r, c, method, d, step;//method 0表示站着，1表示躺着
};
struct Node
{
	int method, d;
	bool vis;
}vis[MAX][MAX];
char map[MAX][MAX];
int R, C, sr, sc, tr, tc, minStep;
int dir[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};//上下右左
queue<node> qq;

bool inmap(int r, int c)
{
	return (r >= 0 && r < R && c >= 0 && c < C && map[r][c] != '#');
}

int bfs()
{
	int i, j, k, newMethod, newd;
	node now, tmp;
	while(!qq.empty())
	{
		now = qq.front();
		qq.pop();
		for(k = 0; k < 4; k++)
		{
			//判断状态
			if(now.method == 0)
			{
				newMethod = 1;
				newd = k;
				i = now.r + dir[k][0];
				j = now.c + dir[k][1];
			}
			else
			{
				if(now.d == k)
				{
					newMethod = 0;
					newd = -1;
					i = now.r + 2 * dir[k][0];
					j = now.c + 2 * dir[k][1];
				}
				else if( (now.d == 1 && k == 0) || (now.d == 0 && k == 1) || (now.d == 2 && k == 3) || (now.d == 3 && k == 2) )
				{
					newMethod = 0;
					newd = -1;
					i = now.r + dir[k][0];
					j = now.c + dir[k][1];
				}
				else
				{
					newMethod = now.method;
					newd = now.d;
					i = now.r + dir[k][0];
					j = now.c + dir[k][1];
				}
			}
			if(!inmap(i, j) || (vis[i][j].vis && vis[i][j].method == newMethod && vis[i][j].d == newd) || (newMethod == 0 && map[i][j] == 'E') || (newMethod == 1 && map[i + dir[newd][0]][j + dir[newd][1]] == '#'))
				continue;
			tmp.r = i;
			tmp.c = j;
			tmp.method = newMethod;
			tmp.d = newd;
			tmp.step = now.step + 1;
			vis[i][j].vis = true; vis[i][j].method = newMethod; vis[i][j].d = newd;
			if(tmp.r == tr && tmp.c == tc && tmp.method == 0)
			{
				if(minStep > tmp.step)
					minStep = tmp.step;
				return minStep;
			}
			qq.push(tmp);
		}
	}
	return -1;
}

int main()
{
	int i, j, flag, firstMethod, firstd, firstdr, firstdc;
	bool first;
	while(scanf("%d %d", &R, &C) == 2)
	{
		if(R == 0 && C == 0)
			break;
		first = true;
		minStep = 999999;
		firstMethod = 0;
		firstd = -1;
		memset(vis, NULL, sizeof(vis));
		for(i = 0; i < R; i++)
		{
			scanf("%s", &map[i]);
			for(j = 0; j < C; j++)
			{
				if(map[i][j] == 'X')
				{
					if(first)
					{
						sr = i;
						sc = j;
						first = false;
					}
					else
					{
						firstMethod = 1;
						firstdr = i - sr;
						firstdc = j - sc;
						if(firstdr == -1 && firstdc == 0)
							firstd = 0;
						else if(firstdr == 1 && firstdc == 0)
							firstd = 1;
						else if(firstdr = 0 && firstdc == 1)
							firstd = 2;
						else
							firstd = 3;
					}
				}
				else if(map[i][j] == 'O')
				{
					tr = i;
					tc = j;
				}
			}
		}
		while(!qq.empty())
			qq.pop();
		node first;
		first.r = sr;
		first.c = sc;
		first.method = firstMethod;
		first.step = 0;
		first.d = firstd;//-1表示站着
		vis[sr][sc].vis = true; vis[sr][sc].method = firstMethod; vis[sr][sc].d = firstd;
		qq.push(first);
		flag = bfs();
		if(flag == -1)
			printf("Impossible\n");
		else
			printf("%d\n", flag);
	}
	return 0;
}

• Re:我的coding超时，我用的STL的queue，哪位能帮我看看哪里可以提高， 感激不尽 (3414) _plxer 2020-07-10 20:58:35