逃离迷宫
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;}
