逃离迷宫

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18702 Accepted Submission(s): 4526

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

       2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3 

Sample Output

       no yes 

做法：每次走一个方向就一直走究竟，路径上假设没訪问过的点，就入队。由于是bfs。每次转向数仅仅添加1，所以最先訪问，就是转向数最少的。入队点假设再直走或者后退。那都是会訪问已经訪问的点，是没意义的，所以必会转向，所以转向数是+1的。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     #define INF 999999999#define eps 0.00001#define LL __int64#define pi acos(-1.0) struct point{ int x,y; int step;//记录转弯数。};int vis[110][110];int n,m;int dir[4][2]={ 1,0, -1,0, 0,1, 0,-1};char mp[110][110];int ok(point nw){ if(nw.x>=0&&nw.x
                      
                       =0&&nw.y
                       
                        q; q.push(sta); while(!q.empty()) { nw=q.front(); if(nw.x==ex&&nw.y==ey) return max(0,nw.step); q.pop(); for(int i=0;i<4;i++) { nex=nw; nex.x+=dir[i][0]; nex.y+=dir[i][1]; nex.step=nw.step+1;//由于是走到了尽头了。所以每一次 //每次step仅仅加1，所以能够用bool vis while(ok(nex)) { if(vis[nex.x][nex.y]==0) { q.push(nex); vis[nex.x][nex.y]=1;//停在这个点。 } nex.x+=dir[i][0]; nex.y+=dir[i][1]; } } } return 999999;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i
                        
                         =ans) printf("yes\n"); else printf("no\n"); } return 0;}/*25 5...***.**...........*....1 1 1 1 35 5...***.**...........*....2 1 1 1 3 */

转载地址：http://jlgoo.baihongyu.com/

你可能感兴趣的文章

MVC 5 Scaffolder + EntityFramework+UnitOfWork Pattern 代码生成工具集成Visual Studio 2013