逃離迷宮
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;}
