逃離迷宮
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34599 Accepted Submission(s): 8478
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
總的來說這道題真的很為難人，要用到廣度優先搜尋。看了很多人的部落格，都沒看懂，是以說編碼習慣真的很重要，要記得寫注釋啊。這道題怎麼說呢，就是從始點開始，上下左右直走，直到沒有路或者到達終點為止，如果是沒有路，就從這條路的最開始開始，上下左右直走，和上一個情況一樣。就這樣将一整個圖周遊完如果還沒有到達終點就沒有方法到達終點，有種回溯法的意思。
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
char map[110][110];
bool vis[110][110];
int sx,sy,ex,ey,n,m,k;//sx,sy,ex,ey,分别是開始的坐标和結束的坐标
int fangxiang[4][2]={-1,0,0,1,1,0,0,-1};
struct node
{
int x,y;
int step;
}s,e; //s為定點，e為擴充點//
//隊列中的一個元素，也就是每個節點包括三個元素，兩個位置元素，一個目前走到目前節點的時候的拐彎次數//
bool judge(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]==\'.\') //判斷目前的擴充節點是否符合要求，既不能走到迷宮外面，不能走有障礙的地方//
return true;
else
return false;
}
void BFS()
{
queue<node>qu;
int i,j;
if(sx==ex&&sy==ey) //如果起點就是終點，那麼輸出然後退出//
{
printf("yes\n");
return;
}
s.x=sx;s.y=sy;s.step=-1; //設定第一個定點//
vis[sx][sy]=true; //标記起點//
qu.push(s);
while(!qu.empty())
{
s=qu.front(); //取起點為定點//
qu.pop(); //彈出//
for(i=0;i<4;i++)
{
int tx=s.x+fangxiang[i][0]; //向四個方向走//
int ty=s.y+fangxiang[i][1];
while(judge(tx,ty)) //如果這個點滿足條件//
{
//是否已經走過，因為該BFS是一次性把某一個方向都搜完，是以如果已經搜尋過，那麼再走這一條路的任何一個定點的時候它都不會轉彎//
if(vis[tx][ty]==false)
{
vis[tx][ty]=true; //标記//
e.x=tx;
e.y=ty;
e.step=s.step+1;
qu.push(e); //擴充點入隊列//
if(e.x==ex&&e.y==ey&&e.step<=k) //每加入一個新的定點，就開始判斷是不是到了終點//
{
printf("yes\n");
return ;
}
}
tx+=fangxiang[i][0];//把一個方向上的所有可以走成路的點搜尋一遍，直到不符合要求
ty+=fangxiang[i][1];
//之是以要把定點的四周的所有的定點都如隊列，是因為，題目中要求了拐彎數，step初始化為-1，第一個定點為起點之後走的第一個點不算是拐彎數,是以+1等于0 。該題的思路也就是運用BFS的同時，考慮到拐彎數這個條件，把step=0的節點先入隊列，因為第一個走的肯定是他們其中的一個,之後再以他們為定點走的擴充點，step一次增加，因為無論向哪個方向走都會拐彎。之後以此類推，把step=1.=2的點都入隊列
}
}
}
printf("no\n");
return ;//必須要有return
//能夠走到終點的條件一個是起點就是終點另一個就是擴充點就是終點，如果這兩個都不是，那麼就是走不到終點，可以退出了//
}
int main()
{
int N;
int i;
while(scanf("%d",&N)!=EOF)
{
while(N--)
{
memset(vis,false,sizeof(vis));//初始化vis
memset(map,0,sizeof(map)); //初始化 map
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
scanf("%s",map[i]+1);
scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);
BFS();
}
}
return 0;
}