HDU 1728 逃离迷宫 bfs 限制k次转弯

3/8/2017来源:ASP.NET技巧人气:933

逃离迷宫

Time Limit: 1000/1000 MS (java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 25472 Accepted Submission(s): 6220

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, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数,(x1, y1), (x2, y2)表示两个位置,其中x1,x2对应列,y1, y2对应行。

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1728

题意

给一个图,限定转弯次数为k次,判定能否从一个点走到另一个点。

题解

记录到达每个点的转弯次数,bfs宽搜。 注意点: (1)同一个方向的路径先入队 (2)题目先先输入列再输入行的!
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #include <stack> #include <queue> #include <vector> #define INF 0x3f3f3f3f using namespace std; //bfs先朝一个方向走到底 const int maxn = 110; int m, n; char pic[maxn][maxn]; int vis[maxn][maxn]; int r0, c0, r1, c1, k; const int dr[]={-1,0,1,0}; const int dc[]={0,1,0,-1}; struct Node{ int r, c, cnt; Node(){} Node(int r, int c, int cnt):r(r), c(c), cnt(cnt){} }; int go(int r, int c){ if(r>=0 && r<m && c>=0 && c<n && pic[r][c] == '.'){ return 1; } return 0; } void solve(){ queue<Node> q; memset(vis, 0, sizeof(vis)); Node st(r0, c0, -1);// i=1时,没有转弯,所以初始值为-1 q.push(st); while(!q.empty()){ Node st = q.front(); q.pop(); for(int i=0; i<4; i++){ int nextr = st.r+dr[i]; int nextc = st.c+dc[i]; while(go(nextr, nextc)){ if( vis[nextr][nextc] == 0){ //遗漏 vis[nextr][nextc] = 1; Node ed(nextr, nextc, st.cnt+1); q.push(ed); if(ed.r == r1 && ed.c == c1 && ed.cnt<=k){ printf("yes\n"); return; } } nextr += dr[i]; nextc += dc[i]; } } } printf("no\n"); } int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d%d", &m, &n); for(int i=0; i<m; i++){ scanf("%s", pic[i]); } scanf("%d%d%d%d%d", &k, &c0, &r0, &c1, &r1); //先输入的是列,再是行 r0--,c0--,r1--,c1--; if(r0 == r1 && c0 == c1) printf("yes\n"); else solve(); } return 0; }