現在的位置: 首頁 > 綜合 > 正文

TopCoder: RevolvingDoors BFS演算法

2013年06月12日 ⁄ 綜合 ⁄ 共 6543字 ⁄ 字型大小 小 中 大 ⁄ 評論關閉

題目來源： RevolvingDoors

感覺這道題比前兩道應用BFS演算法的題目要難一些，不像之前的那麼直接，如果這道題目要求的是最短的頻數的話，那跟前兩道就差不多了，但這裡求的是最少旋轉門的次數，這就有點複雜了，我的思路如下：

1. 判斷當前位置是否是終點，不是則搜索由當前位置可以到達的旋轉門，並將旋轉之後的結果狀態存入LD鏈表尾。

2. 從LD鏈表中取出第一個元素作為當前狀態，重複步驟1.

遇到的問題：BFS演算法需要設置一個訪問狀態標誌，要不然會發生重複搜索同一個狀態的情況，開始的時候我只是設置了一個visited數組確定搜索可到達的旋轉門的過程不會出現重複搜索的過程，結果出現了大問題，因為搜索過程中，進入LD中的元素會有重複的，所以會進行大量的重複搜索，時間複雜度大大增加，而且遇到某些地圖還會出現無限循環的情況，如地圖示例1，而地圖示例2直接就是算半天算不出來，後來我增加了一個 isVisited函數確保進入LD的元素跟以前進入過的元素沒有重複，問題才解決了。

還有一個要注意的問題就是地圖示例的情況不是旋轉6次，而是7次，最後一次也要先旋轉門才能到達終點，開始的程序少算了這一步。

代碼如下：

歡迎大家提出改正意見或者在回復裡面show上自己的代碼微笑

/**
 * TopCoder:RevolvingDoors
 * （http://community.topcoder.com/stat?c=problem_statement&pm=3064&rd=5869）
 * Author: xuzhezhao
 * E-mail: zhezhaoxu@gmail.com
 * Blog: http://blog.csdn.net/xuzhezhaozhao/
 * Date: 2013/6/7
 */

#include <iostream>
#include <string>
#include <list>

using namespace std;

#define MAX 50			/* 地圖無數限制數 */
#define DOORS_MAX 10		/* 門數限制 */

class RevolvingDoors
{
public:
	int turns(string map[]);
};

enum Door_State {H, V};		/* 門的狀態，H：水平 V：豎直 */
typedef struct CurrentPos{
	int row;			/* 當前所處行 */
	int col;			/* 當前所處列 */
	Door_State door[MAX][MAX];	/* 門狀態數組 */
	int door_pos[DOORS_MAX];	/* 門位置信息 */
	int doors_num;			/* 門數量 */
	int turn_doors;			/* trun的門數量 */
}CurrentPos;

static int map_rows = 0;	/* 地圖行數 */
static int map_cols = 0;	/* 地圖列數 */
static int end_row;		/* 終點所在行數 */
static int end_col;		/* 終點所在列數 */
static int visited[MAX][MAX];

void init(string map[], CurrentPos &curpos);
bool isEnd(CurrentPos curpos);
bool isVisited(list <CurrentPos> LV, CurrentPos curpos);

int main()
{
	RevolvingDoors revolvingdoors;
	
	/* 地圖，以 "" 結尾 */
	string map[] = 
	{ 
	"#############",
	"#  #|##|#   #",
	"#   O  O    #",
	"# E || || S #",
	"#    O  O   #",
	"#   #|##|#  #",
	"#############", 
	"" };

	cout << revolvingdoors.turns(map) << endl;
	
	return 0;
}

int RevolvingDoors::turns(string map[])
{
	list <CurrentPos> LC;		/* LC: 內層BFS狀態 */
	list <CurrentPos> LD;		/* LD: 外層BFS，turn 操作之後的狀態 */
	list <CurrentPos> LV;		/* LV：外層BFS訪問狀態標誌，類似visited數組，保存turn操作之後的狀態，以避免重複 */
	CurrentPos curpos, nextpos;
	int row, col;

	init(map, curpos);
	LD.push_back(curpos);

	/* 外層BFS */
	while (!LD.empty()) {
		curpos = LD.front();
		LD.pop_front();

		/* 初始化visited數組 */
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				visited[i][j] = false;
			}
		}

		LC.push_back(curpos);

		/* 內層BFS */
		while (!LC.empty()) {
			curpos = LC.front();
			LC.pop_front();
			row = curpos.row;
			col = curpos.col;
			visited[row][col] = true;

			if (isEnd(curpos)) {
				return curpos.turn_doors;
			}

			/* 可以向上下左右四個方向推進狀態 */

			/* 向上走 */
			nextpos = curpos;
			if (row - 1 >= 0 && !visited[row-1][col]) {
				nextpos.row = row - 1;

				if (' ' == map[row-1][col]) {
					LC.push_back(nextpos);
				} else if ('*' == map[row-1][col]) {	/* 進入門的四周區域 */
					/* 門的位置有三種情況 */
					if (row - 2 >= 0 && 'O' == map[row-2][col] && H == curpos.door[row-2][col] ) {
						LC.push_back(nextpos);
					} else if (col + 1 <= map_cols - 1 && 
						'O' == map[row-1][col+1]) {
						if (V == curpos.door[row-1][col+1]) {
							LC.push_back(nextpos);
						} else {	/* turn door */
							nextpos.door[row-1][col+1] = V;
							++nextpos.turn_doors;
							visited[row-1][col] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					} else if (col - 1 >= 0 && 'O' == map[row-1][col-1]) {
						if (V == curpos.door[row-1][col-1]) {
							LC.push_back(nextpos);
						} else {
							nextpos.door[row-1][col-1] = V;
							++nextpos.turn_doors;
							visited[row-1][col] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					}
				}
			}

			/* 向下走 */
			nextpos = curpos;
			if (row + 1 <= map_rows - 1 && !visited[row+1][col]) {
				nextpos.row = row + 1;
				if (' ' == map[row+1][col]) {
					LC.push_back(nextpos);
				} else if ('*' == map[row+1][col]) {
					if (row + 2 <= map_rows - 1 && 'O' == map[row+2][col] &&
						H == curpos.door[row+2][col] ) {
						LC.push_back(nextpos);
					} else if (col + 1 <= map_cols - 1 && 'O' == map[row+1][col+1]) {
						if (V == curpos.door[row+1][col+1]) {
							LC.push_back(nextpos);
						} else {	/* turn door */
							nextpos.door[row+1][col+1] = V;
							++nextpos.turn_doors;
							visited[row+1][col] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					} else if (col - 1 >= 0 &&
						'O' == map[row+1][col-1]) {
						if (V == curpos.door[row+1][col-1]) {
							LC.push_back(nextpos);
						} else {
							nextpos.door[row+1][col-1] = V;
							++nextpos.turn_doors;
							visited[row+1][col] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					}
				}
			}

			/* 向左走 */
			nextpos = curpos;
			if (col - 1 >= 0 && !visited[row][col-1]) {
				nextpos.col = col - 1;
				if (' ' == map[row][col-1]) {
					LC.push_back(nextpos);
				} else if ('*' == map[row][col-1]) {
					if (col - 2 >= 0 && 'O' == map[row][col-2] &&
						V == curpos.door[row][col-2] ) {
						LC.push_back(nextpos);
					} else if (row - 1 >= 0 && 
						'O' == map[row-1][col-1]) {
						if (H == curpos.door[row-1][col-1]) {
							LC.push_back(nextpos);
						} else {	/* turn door */
							nextpos.door[row-1][col-1] = H;
							++nextpos.turn_doors;
							visited[row][col-1] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					} else if (row + 1 <= map_rows - 1 && 'O' == map[row+1][col-1]) {
						if (H == curpos.door[row+1][col-1]) {
							LC.push_back(nextpos);
						} else {
							nextpos.door[row+1][col-1] = H;
							++nextpos.turn_doors;
							visited[row][col-1] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					}
				}
			}

			/* 向右走 */
			nextpos = curpos;
			if (col + 1 <= map_cols - 1 && !visited[row][col+1]) {
				nextpos.col = col + 1;
				if (' ' == map[row][col+1]) {
					LC.push_back(nextpos);
				} else if ('*' == map[row][col+1]) {
					if (col + 2 <= map_cols - 1 && 'O' == map[row][col+2] &&
						V == curpos.door[row][col+2] ) {
							LC.push_back(nextpos);
					} else if (row + 1 <= map_rows - 1 && 
						'O' == map[row+1][col+1]) {
						if (H == curpos.door[row+1][col+1]) {
							LC.push_back(nextpos);
						} else {	/* turn door */
							nextpos.door[row+1][col+1] = H;
							++nextpos.turn_doors;
							visited[row][col+1] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					} else if (row - 1 >= 0 &&
						'O' == map[row-1][col+1]) {
						if (H == curpos.door[row-1][col+1]) {
							LC.push_back(nextpos);
						} else {
							nextpos.door[row-1][col+1] = H;
							++nextpos.turn_doors;
							visited[row][col+1] = true;
							if (!isVisited(LV, nextpos)){
								LV.push_back(nextpos);
								LD.push_back(nextpos);
							}
						}
					}
				}
			}
		}
	}
	return -1;
}

/**
 * 初始操作，獲得地圖的基本信息，行，列，門狀態。並將門四周的4個點置為 '*' 字元，將 S， E 置為' '(空格)。
 */
void init(string map[], CurrentPos &curpos)
{
	int i, j;
	
	curpos.turn_doors = 0;

	while (map[map_rows] != "") {
		++map_rows;
	}
	if (map_rows > 0) {
		map_cols = map[0].length();
	}

	for (i = 0; i < map_rows; i ++) {
		for (j = 0; j < map_cols; j++) {
			if ('S' == map[i][j]) {
				curpos.row = i;
				curpos.col = j;
				map[i][j] = ' ';
			}
			if ('E' == map[i][j]) {
				end_row = i;
				end_col = j;
				map[i][j] = ' ';
			}
		}
	}
	curpos.doors_num = 0;
	for (i = 0; i < map_rows; i ++) {
		for (j = 0; j < map_cols; j++) {
			if ('O' == map[i][j]) {
				curpos.door_pos[curpos.doors_num] = i * map_cols + j;
				++curpos.doors_num;
				if ('|' == map[i+1][j]) {
					curpos.door[i][j] = V;
				} else {
					curpos.door[i][j] = H;
				}
				map[i+1][j] = map[i-1][j] =
					map [i][j+1] = map[i][j-1] = '*';
			}
		}
	}
}

/**
 * 判斷是否到達終點
 */
bool isEnd(CurrentPos curpos)
{
	if (curpos.row == end_row && curpos.col == end_col) {
		return true;
	} else {
		return false;
	}
}

/**
 * 外層BFS訪問標誌，若LV中含有curpos狀態，返回true，否則返回false
 */
bool isVisited(list <CurrentPos> LV, CurrentPos curpos)
{
	list<CurrentPos>::iterator it;
	int door_row, door_col;
	bool flag;
	if (LV.empty()) {
		return false;
	}
	for (it = LV.begin(); it != LV.end(); it++) {
		if (it->row == curpos.row && it->col == curpos.col) {
			flag = true;
			for (int i = 0; i < curpos.doors_num; i++) {
				door_row = curpos.door_pos[i] / map_cols;
				door_col = curpos.door_pos[i] % map_cols;
				if (it->door[door_row][door_col] != curpos.door[door_row][door_col]) {
					flag = false;
					break;
				}
			}
			if (flag) {
				return true;
			}
		}
	}
	return false;
}

返回
【上篇】
【下篇】

作者:

抱歉!評論已關閉.

返回首頁

Copyright © 2013-2018 學步園  保留所有權利.
軟文銷售 QQ客服：2265327166 點擊這裡給我發消息（其他合作也可洽談）
必威體育
必威電競