逃离迷宫

给定一个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 ≤ x1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数，(x 1, y 1), (x 2, y2)表示两个位置，其中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

DFS

#include<stdio.h>
#include<string.h>
int m, n, k, x1, x2, y1, y2, h;
int g[4][2] = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
int  b[110][110];
char a[110][110];
void DFS(int x, int y, int f)  // f当前方向     
{
	if (b[x][y] > k || (x != x2&&y != y2&&b[x][y] == k)) return;
	if (x == x2&&y == y2&&b[x][y] <= k)
	{
		h = 1;
		return;
	}
	for (int i = 0; i < 4; i++)        //   向 右，左，上，下，四个方向搜索
	{	
		int xx = x + g[i][0];
		int yy = y + g[i][1];
		if (a[x + g[i][0]][y + g[i][1]] == '*' || x + g[i][0] <1 || x + g[i][0] >m || y + g[i][1]<1 || y + g[i][1]>n)  //  不越界 且 可走
			continue;	
		if (b[xx][yy] < b[x][y])  //  说明访问过
			continue;
		if (f != -1 && b[xx][yy] == b[x][y] && f != i)
			continue;  //  传入得点以前走过的，现在的是从另一条路到达的该点，且传入方向与将要行走的方向不同，所以舍弃该路！			
		if (f != -1 && f != i) b[xx][yy] = b[x][y] + 1;
		else b[xx][yy] = b[x][y];
		DFS(xx, yy, i);
		if (h) return;
	}
}
int main()
{
	int t;
	//freopen("\\1.in", "r", stdin);
	scanf("%d", &t);
	while (t--)
	{
		char s[110];
		scanf("%d%d", &m, &n);
		getchar();
		for (int i = 1; i <=m; i++)
		{
			scanf("%s", &s);
			strcpy(a[i], " ");
			strcat(a[i], s);
			getchar();
		}
		scanf("%d%d%d%d%d", &k, &y1, &x1, &y2, &x2);  //  y 列 x 行
		for (int i = 1; i <=m; i++)
		for (int j = 1; j <=n; j++)
		{
			b[i][j] = 10010;
		}
		b[x1][y1] = 0; h = 0;
		DFS(x1, y1, -1);
		if (h) printf("yes\n");
		else  printf("no\n");
	}
	return 0;
}

BFS

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>

using namespace std;



int t,m,n;
int k,x1,x2,y1,y2;
char dfs[110][110];
int vis[110][110];
int a[4]={1,-1,0,0};
int b[4]={0,0,1,-1};
bool flag;


struct node
{
     int x;
     int y;
     int lev;
     int f;
}front1,tmp,start,end1;
    queue <node>Q;


void bfs(node s,node e){

    while(!Q.empty())
        Q.pop();

    if(s.x==x2&&s.y==y2&&s.lev<=k)
        {   //Q.push(s);
            flag=true;
            return;
        }
	Q.push(s);
    while(!Q.empty()){
        front1=Q.front();
        Q.pop();

        for(int i=0;i<4;i++){

            tmp.x=a[i]+front1.x;
            tmp.y=b[i]+front1.y;
			tmp.lev=front1.lev;
							
            if(front1.f!=-1&&front1.f!=i)
                	tmp.lev++;
            tmp.f=i;
			if(tmp.x<1||tmp.x>n||tmp.y<1||tmp.y>m||dfs[tmp.y-1][tmp.x-1]=='*') continue;           
            if(e.x==tmp.x&&e.y==tmp.y&&tmp.lev<=k){
            	//printf("%d  %d %d\n",tmp.x,tmp.y,tmp.lev);
            	flag=true;
            	return;
            	
			}       
			            
            if(vis[tmp.y][tmp.x]==0&&tmp.lev<=k){            	
 					vis[tmp.y][tmp.x]=1;
               	printf("%d  %d %d %d\n",tmp.x,tmp.y,tmp.lev,i);
                	Q.push(tmp);
          	}
        }
    }
}

int main()
{
    scanf("%d",&t);
    while(t--){
        memset(vis,0,sizeof(vis));
        memset(dfs,'0',sizeof(dfs));
        scanf("%d%d",&m,&n);
        for(int i=0;i<m;i++)
            scanf("%s",dfs[i]);
        scanf("%d%d%d%d%d",&k,&x1,&y1,&x2,&y2);
        //flag=-1;
                vis[x1][y1]=1;
                start.x=x1;
                start.y=y1;                
                start.lev=0;              
                start.f=-1;
                
                end1.x=x2;
                end1.y=y2;
                
                flag=false ;
                bfs(start,end1);
                
                
            flag?printf("yes\n"):printf("no\n");

    }
    return 0;
}