程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 杭電ACM1180——詭異的樓梯~~廣度優先搜索

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

編輯:C++入門知識

杭電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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved