hdoj 1728 逃离迷宫【BFS】

不念不忘少年蓝@ 2022-08-10 05:47 164阅读 0赞

# 逃离迷宫 #

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 20352    Accepted Submission(s): 4946**

Problem Description

给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？

Input

第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，  
　　第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'\*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x 1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数，(x 1, y 1), (x 2, y 2)表示两个位置，其中x 1，x 2对应列，y 1, y 2对应行。

Output

每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。

Sample Input

2
    5 5
    ...**
    *.**.
    .....
    .....
    *....
    1 1 1 1 3
    5 5
    ...**
    *.**.
    .....
    .....
    *....
    2 1 1 1 3

Sample Output

no
    yes

【注意：最后输入的两对数，先输入列数，再输入行数】；

因为本题主要考虑的有方向和转弯次数，所以定义一个struct

struct Node \{

int r, c;          //横坐标和纵坐标

int dir, num;  //记录反向和转弯次数

Node(int r, int c, int dir, int num) : r(r), c(c), dir(dir), num(num) \{\}

\}；//若不懂该结构体中的具体意义，可参考 [http://blog.csdn.net/nailnehc/article/details/47313649][http_blog.csdn.net_nailnehc_article_details_47313649]

思路：从给出的两个点中选一个作为起点，一个作为终点，先遍历起点四个方向上的邻点，检查是否越界和是否可行，只有不越界&&可以行走，则把该点信息入队，然后开始一系列的出对入队操作，直到队空

出队入队具体操作{
    	出队队首元素 && pop();
    	队首元素 包括{r, c, dir, num};
    	遍历该点的四个方向{ 
    		判断是否越界 && 可行 
    		不越界&&可行 { 
    			if(转弯数超限)
    				continue;
    			if(已走过 && 当前转弯数比之前走过的要多)
    				continue;
    			if(已经到达终点)
    				返回true
    			对应的vis标记为true；
    			记录走到该点该方向上的转弯数；
    			记录入队 ； 
    		}
    	} 
    }

已Accept代码【c++提交】

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    int dx[] = {1, 0, -1, 0};	//房前位置的四个方向
    int dy[] = {0, 1, 0, -1};
    int n, m;
    int k, c1, c2, r1, r2;
    int dis[101][101][4];
    bool vis[101][101][4];
    char map[101][101];
    struct Node {
    	int r, c;
    	int dir, num;
    	Node(int r, int c, int dir, int num) : r(r), c(c), dir(dir), num(num) {}
    };
    
    bool BFS() {
    	queue <Node> Q;
    	memset(vis, 0, sizeof(vis));
    	for(int i = 0; i < 4; i++) {
    		int x = r1 + dx[i], y = c1 + dy[i];
    		if(x == r2 && y == c2)
    				return true;
    		if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == '.') {
    			Q.push(Node(x, y, i, 0));
    			vis[x][y][i] = true;
    		}
    	}
    	while(!Q.empty()) {
    		Node node = Q.front();
    		Q.pop();	//记得删除队首
    		int r = node.r, c = node.c, dir = node.dir, num = node.num;
    		for(int i = 0; i < 4; i++) {
    			int x = r + dx[i];
    			int y = c + dy[i];
    			if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == '.') {
    				int n_num = i == dir ? num : num + 1;	//判断是否转向
    				if(n_num > k)
    					continue;
    				if(vis[x][y][i] && n_num >= dis[x][y][i])
    					continue;
    				if(x == r2 && y == c2)
    					return true;
    				vis[x][y][i] = true;
    				dis[x][y][i] = n_num;
    				Q.push(Node(x, y, i, n_num));
    			}
    		}
    	}
    	return false;
    }
    
    int main() {
    	int t;
    	scanf("%d",&t);
    	while(t--) {
    		scanf("%d%d", &n, &m);
    		for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++)
                    scanf(" %c", &map[i][j]);
            }
    		scanf("%d%d%d%d%d", &k, &c1, &r1, &c2, &r2);	//注意输入顺序
    		if(BFS())
    			printf("yes\n");
    		else
    			printf("no\n");
    	}
    	return 0;
    }

[http_blog.csdn.net_nailnehc_article_details_47313649]: http://blog.csdn.net/nailnehc/article/details/47313649