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

 

Output

　　每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。

 

Sample Input

 

Sample Output

 

Source

“网新恩普杯”杭州电子科技大学程序设计邀请赛

 

Recommend

lcy   |   We have carefully selected several similar problems for you:  1253 1072 1026 1372 1180 

 

 

题解：

dfs，记得用vis记录，防止重复搜索

 #include <cstdio>

 #include <cstring>

 #include <stack>

 #include <vector>

 #include <map>

 #include <algorithm>

 #define ll long long

 int const N = ;

 int const M = ;

 int const inf = ;

 ll const mod = ;

 using namespace std;

 int T;

 int n,m;

 int k;

 int vis[N][N][][];

 struct PP

 {

     int x;

     int y;

     int operator ==(const PP &b) const

     {

         if(x==b.x && y==b.y) return ;

         else return ;

     }

 };

 PP st,en;

 char s[N][N];

 int dirx[]={-,,,};

 int diry[]={,,,-};

 int flag;

 void ini()

 {

     int i,j;

     flag=;

     scanf("%d%d",&n,&m);

     memset(vis,,sizeof(vis));

     for(i=;i<=n+;i++){

         for(j=;j<=m+;j++){

             s[i][j]='*';

         }

     }

     for(i=;i<=n;i++){

         scanf("%s",s[i]+);

     }

     scanf("%d%d%d%d%d",&k,&st.y,&st.x,&en.y,&en.x);

 }

 void dfs(PP te,int d,int num)

 {

     if(num>k){

         return;

     }

     if(te==en){

         flag=;return;

     }

     int i;

     PP nt;

     for(i=;i<;i++){

         nt.x=te.x+dirx[i];

         nt.y=te.y+diry[i];

         if(s[nt.x][nt.y]=='.'){

             if(i==d){

                 if(vis[nt.x][nt.y][num][i]==) continue;

                 vis[nt.x][nt.y][num][i]=;

                 dfs(nt,i,num);

             }

             else{

                 if(vis[nt.x][nt.y][num+][i]==) continue;

                 vis[nt.x][nt.y][num+][i]=;

                 dfs(nt,i,num+);

             }

             if(flag==) return;

         }

     }

 }

 void solve()

 {

     int d;

     PP nt;

     if(nt==en){

         flag=;return;

     }

     for(d=;d<;d++){

         if(flag==) return;

         nt.x=st.x+dirx[d];

         nt.y=st.y+diry[d];

         if(s[nt.x][nt.y]=='.'){

             vis[nt.x][nt.y][][d]=;

             dfs(nt,d,);

         }

     }

 }

 void out()

 {

     if(flag==){

         printf("yes\n");

     }

     else{

         printf("no\n");

     }

 }

 int main()

 {

     //freopen("data.in","r",stdin);

    // freopen("data.out","w",stdout);

     scanf("%d",&T);

     //for(int cnt=1;cnt<=T;cnt++)

     while(T--)

     //while(scanf("%d%d",&n,&sum)!=EOF)

     {

         ini();

         solve();

         out();

     }

 }