杭電ACM1180——詭異的樓梯~~廣度優先搜索

杭電ACM1180——詭異的樓梯~~廣度優先搜索

這一題，簡單的廣搜就可以搞定，只是在搜索的時候判斷比較麻煩，遇到樓梯的時候，有多種情況，停下來等，或者走其他路，來到樓梯，樓梯是否可以直接上等等的判斷。

一開始WR，就是在樓梯可以直接上的時候，沒有判斷走出樓梯的那一個是否可以走，所以WR了3次。

下面AC的代碼：

#include 
#include 
using namespace std;

class Node
{
public:
	int x, y, time;
};
int M, N;
char map[25][25];
int vis[25][25];
int xy[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
int start_x, start_y, end_x, end_y;
queue  que;
Node node;
int bfs()
{
    int fx, fy;
	node.x = start_x;
	node.y = start_y;
	node.time = 0;
	que.push(node);
	while(!que.empty())
	{
		node = que.front();
		que.pop();
		if(node.x == end_x && node.y == end_y)   //到達終點
		{
			return node.time;
		}
		for(int i = 0; i < 4; i++)
		{
			fx = node.x + xy[i][0];
			fy = node.y + xy[i][1];
			if(fx >= 0 && fx < M && fy >= 0 && fy < N && map[fx][fy] != '*' && !vis[fx][fy])
			{
				if(map[fx][fy] == '.' || map[fx][fy] == 'T')
				{
					Node temp;
					temp.x = fx; temp.y = fy; temp.time = node.time + 1;
					que.push(temp);
					vis[fx][fy] = 1;
				}
				else if(map[fx][fy] == '-')           //開始樓梯橫向
				{
					if(node.time % 2 == 0)         //偶數時間
					{
						if(fx == node.x)      //判斷是否是橫向走過來的
						{
							if(node.y + 1 == fy) //向右走
								fy = fy + 1;
							else               //向左走
								fy = fy - 1;
							if(fy >= 0 && fy < N && map[fx][fy] != '*' && !vis[fx][fy])  //判斷走過樓梯之後的那個是否可以走
							{
								Node temp;
								temp.x = fx; temp.y = fy; temp.time = node.time + 1;
								que.push(temp);
								vis[fx][fy] = 1;
							}
						}
						else                  //停留等樓梯的情況
						{
							Node temp;
							temp.x = node.x; temp.y = node.y; temp.time = node.time + 1;
							que.push(temp);
						}
					}
					else                              //奇數時間
					{
						if(fy == node.y)             //判是否豎向走的
						{
							if(node.x + 1 == fx) //向下走的情況
								fx = fx + 1;
							else                //向上的情況
								fx = fx - 1;
							if(fx >= 0 && fx < M && map[fx][fy] != '*' && !vis[fx][fy])  //同上
							{
								Node temp;
								temp.x = fx; temp.y = fy; temp.time = node.time + 1;
								que.push(temp);
								vis[fx][fy] = 1;
							}
						}
						else   //停留
						{
							Node temp;
							temp.x = node.x; temp.y = node.y; temp.time = node.time + 1;
							que.push(temp);
						}
					}
				}
				else if(map[fx][fy] == '|')  //同上
				{
					if(node.time % 2 == 0)
					{
						if(fy == node.y)
						{
							if(node.x + 1 == fx)
								fx = fx + 1;
							else 
								fx = fx - 1;
							if(fx >= 0 && fx < M && map[fx][fy] != '*' && !vis[fx][fy])
							{
								Node temp;
								temp.x = fx; temp.y = fy; temp.time = node.time + 1;
								que.push(temp);
								vis[fx][fy] = 1;
							}
						}
						else
						{
							Node temp;
							temp.x = node.x; temp.y = node.y; temp.time = node.time + 1;
							que.push(temp);
						}
					}
					else
					{
						if(fx == node.x)
						{
							if(node.y + 1 == fy)
								fy = fy + 1;
							else
								fy = fy - 1;
							if(fy >= 0 && fy < N && map[fx][fy] != '*' && !vis[fx][fy])
							{
								Node temp;
								temp.x = fx; temp.y = fy; temp.time = node.time + 1;
								que.push(temp);
								vis[fx][fy] = 1;
							}
						}
						else 
						{
							Node temp;
							temp.x = node.x; temp.y = node.y; temp.time = node.time + 1;
							que.push(temp);
						}
					}
				}
			}
		}
	}
}

int main()
{
    while(cin >> M >> N)
    {
        for(int i = 0; i < M; i++)
        {
            for(int j = 0; j < N; j++)
            {
                cin >> map[i][j];
				vis[i][j] = 0;
                if(map[i][j] == 'S' || map[i][j] == 's')   //標記起點的位置
                {
                    start_x = i;
                    start_y = j;
                }
                if(map[i][j] == 'T' || map[i][j] == 't')   //標記終點位置
                {
                    end_x = i;
                    end_y = j;
                }
            }
        }
		vis[start_x][start_y] = 1;
		while(!que.empty())
		{
			que.pop();
		}
        int ans = bfs();
        cout << ans << endl;
    }
    return 0;
}