ACM2579——Dating with girls(2)

@TOCACM2579 —— 如何使用图的广度优先搜索？

前言

Dating with girls(2) ：
If you have solved the problem Dating with girls(1).I think you can solve this problem too.This problem is also about dating with girls. Now you are in a maze and the girl you want to date with is also in the maze.If you can find the girl, then you can date with the girl.Else the girl will date with other boys. What a pity!
The Maze is very strange. There are many stones in the maze. The stone will disappear at time t if t is a multiple of k(2<= k <= 10), on the other time , stones will be still there.
There are only ‘.’ or ‘#’, ’Y’, ’G’ on the map of the maze. ’.’ indicates the blank which you can move on, ‘#’ indicates stones. ’Y’ indicates the your location. ‘G’ indicates the girl’s location . There is only one ‘Y’ and one ‘G’. Every seconds you can move left, right, up or down.

input :
1
6 6 2
…Y…
…#…
.#…
…#…
…#…
…#G#.
output:
7
题目的大致意思就是：求解从Y-G所需最短时间是多少？

这个ACM题是很经典的图论搜索： 广度优先搜素算法

广度优先遍历算法的探讨

以下图片是从博客借鉴的，因为懒得画图：

图的广度优先遍历核心思想是QUEUE操作：
1、VISIT 源节点（0）；同时queue.push(0)
2、节点0出队，同时VISIT 节点0的子节点5、1、2、6，并把他们入队
3、节点5出队，同时VISIT 节点5的子节点3、4，并把他们入队
说明： 如果目的节点是4，此时dst(0->4) = 2
4、节点1 、2出队，由于没有子节点，没有后续入队操作
5、节点6出队，节点4已经在队列中且已经访问过了，不需要重复操作
5、节点3、4出队。

C++实现代码

有些特殊情况需要考虑，已写注释

// An highlighted block
#include <iostream>
#include <string.h>
#include <queue>

#define MAX_MAP_LEN   100
#define MAX_VISIT_LEN 10000
#define DRECTION_LEN  4
using namespace std;

typedef struct {
	int x;
	int y;
}Position;
int g_timeK;
int g_visitMap[MAX_MAP_LEN][MAX_MAP_LEN];
int g_visitTime[MAX_MAP_LEN][MAX_MAP_LEN];
queue<Position> g_queueVisit;
//上下左右四个方向数组
int g_drection[][DRECTION_LEN] = {{-1, 1, 0, 0},
								  {0, 0, -1, 1}};

int getWaitStoneTime(int curTime)
{
	int addTime = MAX_VISIT_LEN;
	for(int i = 0; i <= g_timeK; ) {
		if (((curTime + i) % g_timeK) == 0) {
			addTime = i;
			break;
		}
		i += 2;
	}
	return addTime;
}

// 图的广度优先遍历
void GetMinRouteBriwth(Position sourcePosition, int curArray[][MAX_MAP_LEN], int row, int col)
{
	g_queueVisit.push(sourcePosition);
	int addTime = MAX_VISIT_LEN;
	int tempTime = MAX_VISIT_LEN;
	Position nextPosition;
	while(!g_queueVisit.empty()) {
		Position topItem = g_queueVisit.front();
		g_queueVisit.pop();
		if (curArray[topItem.x][topItem.y] == 4)
		{
			continue;
		}
		// 被石头包围直接走不动了
		bool isStone = true;
		for (int i = 0; i < DRECTION_LEN; i++) {
			if ((topItem.x + g_drection[0][i] >= 0) && (topItem.x + g_drection[0][i] < row) &&
				(topItem.y + g_drection[1][i] >= 0) && (topItem.y + g_drection[1][i] < col)) {
					if (curArray[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] != 1) {
						isStone = false;
						break;
					}
			}
		}
		if (isStone) {
			continue;
		}

		for (int i = 0; i < DRECTION_LEN; i++) {
			if ((topItem.x + g_drection[0][i] < 0) || (topItem.x + g_drection[0][i] >= row) ||
				(topItem.y + g_drection[1][i] < 0) || (topItem.y + g_drection[1][i] >= col)) {
					// 越界处理
					continue;
			}
			if (curArray[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] == 1) {
				// 如果当前位置是石头，下一秒肯定去不到下一个是石头的位置
				if (curArray[topItem.x][topItem.y] == 1) {
					continue;
				}
				addTime = getWaitStoneTime(g_visitTime[topItem.x][topItem.y] + 1);
				// 下一个石头位置始终不能VISIT
				if (addTime == MAX_VISIT_LEN) {
					continue;
				}
			}
			else {
				addTime = 0;
			}
			tempTime = g_visitTime[topItem.x][topItem.y] + 1 + addTime;
			if (g_visitMap[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] == 0) {
				g_visitTime[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] = tempTime;
				g_visitMap[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] = -1;
				nextPosition.x = topItem.x + g_drection[0][i];
				nextPosition.y = topItem.y + g_drection[1][i];
				g_queueVisit.push(nextPosition);
			}
			else {
				if (g_visitTime[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] > tempTime) {
					g_visitTime[topItem.x + g_drection[0][i]][topItem.y + g_drection[1][i]] = tempTime;
					nextPosition.x = topItem.x + g_drection[0][i];
					nextPosition.y = topItem.y + g_drection[1][i];
					g_queueVisit.push(nextPosition);
				}
			}
		}
	}
}

int main()
{
	int testCases;
	int row, clonum;
	int stoneArray[MAX_MAP_LEN][MAX_MAP_LEN];
	cin>>testCases;
	for (int i = 0; i < testCases; i++) {
		cin>>row>>clonum>>g_timeK;
		for (int j = 0; j < MAX_MAP_LEN; j++) {
			(void)memset(stoneArray[j], 0, sizeof(int)*MAX_MAP_LEN);
			(void)memset(g_visitMap[j], 0, sizeof(int)*MAX_MAP_LEN);
			for (int k = 0; k < MAX_MAP_LEN; k++) {
				g_visitTime[j][k] = MAX_VISIT_LEN;
			}
		}
		char tempChar;
		Position yourLocation, girlLocation;
		for (int p = 0; p < row; p++) {
			for (int q = 0; q < clonum; q++) {
				cin>>tempChar;
				if (tempChar == 'Y') {
					yourLocation.x = p;
					yourLocation.y = q;
					stoneArray[p][q] = 3;
					g_visitMap[p][q] = -1;
					g_visitTime[p][q] = 0;
				}
				else if (tempChar == 'G') {
					girlLocation.x = p;
					girlLocation.y = q;
					stoneArray[p][q] = 4;
				}
				else if (tempChar == '#') {
					if (g_timeK > 1) {
						stoneArray[p][q] = 1;
					}
				}
				else {
					//do nothing
				}
			}
		}
		GetMinRouteBriwth(yourLocation, stoneArray, row, clonum);
		if (g_visitTime[girlLocation.x][girlLocation.y] == MAX_VISIT_LEN) {
			cout<<"Please give me another chance!"<<endl;
		}
		else {
			cout<<g_visitTime[girlLocation.x][girlLocation.y]<<endl;
		}
	}

    return 0;
}

说明

版权考虑，如果转载请注明出处，谢谢！