呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

hdu 1175:连连看(dfs 深度优先搜索)

连连看

Time Limit : 20000/10000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 4   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

“连连看”相信很多人都玩过。没玩过也没关系,下面我给大家介绍一下游戏规则:在一个棋盘中,放了很多的棋子。如果某两个相同的棋子,可以通过一条线连起来(这条线不能经过其它棋子),而且线的转折次数不超过两次,那么这两个棋子就可以在棋盘上消去。不好意思,由于我以前没有玩过连连看,咨询了同学的意见,连线不能从外面绕过去的,但事实上这是错的。现在已经酿成大祸,就只能将错就错了,连线不能从外围绕过。
玩家鼠标先后点击两块棋子,试图将他们消去,然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。

Input

输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000),分别表示棋盘的行数与列数。在接下来的n行中,每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子,正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50),表示下面有q次询问。在接下来的q行里,每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时,输入结束。
注意:询问之间无先后关系,都是针对当前状态的!

Output

每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

Sample Input

3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0

Sample Output

YES
NO
NO
NO
NO
YES


NOTE:

 连连看大家都玩过,这道题就是判断指定两格能不能消掉。
 与我们玩过的连连看不同的是它不可以从矩阵外面连线。
 这道题重点在于递归函数,每一次递归代表移动一步,多次递归,直到找到一条可行的路径。如果没有可行路径,返回false。
 递归函数原型:
 bool f(int x1,int y1,int x2,int y2,int n,int m,int turns,Direction D); //判断两点能否相连
 另外这道题需要注意有许多限制条件存在,例如下一步所在方格不能是0外的其他数字,例如下一步不能出界等等。
 这些限制条件大体有两种情况:
  1、每一次都需要判断的。
  2、只需判断一次的。

 每一次都需要判断的:
  1) 弯折次数是否超过2次。
  2) 当前是否出界。
  3) 坐标代表的2点是否重叠,重叠了代表找到一条路径。(已排除开始重叠的情况)
  4) 判断当前点是否为0
 只需判断一次的:
  1) 判断询问两点是否重叠
  2) 判断询问两点是否都有棋子,即是否有一个棋子为0,如果是,推出本次询问。

 每一次都需要判断的放在递归函数前面每次先判断一遍,只需判断一次的放在递归函数外,询问坐标输入之后先判断一遍在进入递归。
 接下来就是移动了,需要注意的是如果你正在向右走,你只能继续向右或者向上向下三个方向而不能往回走。例:
 switch(D){
  ……
  Case RIGHT:  //当前为向右走
   //下一步向上走,弯折 turns+1
      if(f(x1-1,y1,x2,y2,n,m,turns+1,UP)) return true;
           //向右走,同方向
           else if(f(x1,y1+1,x2,y2,n,m,turns,RIGHT)) return tru
          //向下走,弯折 turns+1
          else if(f(x1+1,y1,x2,y2,n,m,turns+1,DOWN)) return true;
          //如果三个方向都不通,则返回false
          else return false;
  ……
 }

 

  1 #include <iostream>
  2 using namespace std;
  3 int a[1001][1001];      //注意将数组的定义放在外面,否则会出错。
  4 int turns=0;            //弯折次数  
  5 enum Direction{         //定义枚举变量,代表移动状态 
  6      UP,
  7      RIGHT,
  8      DOWN,
  9      LEFT,
 10      STAY
 11 };                                  
 12 int main()
 13 {
 14     bool f(int ,int ,int ,int ,int ,int ,int ,Direction);
 15     Direction D = STAY;
 16     int n,m,i,j,q;
 17     int x1,y1,x2,y2;
 18     while(cin>>n>>m){   //输入n,m (0<n<=1000,0<m<1000)
 19         if(n==0 && m==0) break;     //如果n=0 且 m=0 则输入结束
 20         for(i=1;i<=n;i++)           //输入n,m之后,依次输入矩阵
 21             for(j=1;j<=m;j++)
 22                 cin>>a[i][j];
 23         cin>>q;     //矩阵输入完成后,输入询问次数q(0<q<50)
 24         while(q--){     //循环q次,每次为一次询问
 25             //输入本次询问的两点坐标
 26             cin>>x1>>y1>>x2>>y2;
 27             if(x1==x2 && y1==y2) {cout<<"NO"<<endl;continue;}       //判断询问两点是否重合,若重合,输出NO 
 28             //判断询问两点类型是否相同。不同,则返回false;相同,继续向下判断。
 29             if(a[x1][y1]!=a[x2][y2]) {cout<<"NO"<<endl;continue;}
 30             //判断询问两点是否都有棋子,即判断这两点是否有一个是0或者都为0,若是,则返回false;若不是,继续向下判断。
 31             if(a[x1][y1]==0 || a[x2][y2]==0) {cout<<"NO"<<endl;continue;}
 32             turns=0;
 33             D=STAY;
 34             if(f(x1,y1,x2,y2,n,m,turns,D))  //每次询问,调用函数f(x1,y1,x2,y2)判断这两点能否相连
 35                 cout<<"YES"<<endl;  //如果可以,输出YES
 36             else
 37                 cout<<"NO"<<endl;   //如果不可以,输出NO
 38         }
 39     }
 40     return 0;
 41 }
 42 bool f(int x1,int y1,int x2,int y2,int n,int m,int turns,Direction D)     //返回两点能否相连
 43 {
 44     //弯折次数如果超过2次,返回false。 
 45     if(turns>2) return false;
 46     //不管开没开始移动,都判断有没有出界。出界,则返回false;没有出界,继续向下判断。
 47     if((x1<1 || x1>n) || (x2<1 || x2>n) || (y1<1 || y1>m) || (y2<1 || y2>m)) return false;
 48     //不管开没开始移动,都判断询问两点是否重合,且已经排除开始重合的情况。所以这里只能是移动后重合的情况,若移动后重合,则说明到达指定地点,返回true.
 49     if( x1==x2 && y1==y2 ) return true;
 50     //已经开始移动的时候,判断落子处是否为0。若不是0,则返回false;是0,表示可以移动,继续向下判断。
 51     if(D!=STAY && a[x1][y1]!=0) return false;
 52     switch(D){
 53         case UP:  //当前是向上走 
 54              //下一步向上走,同方向 
 55              if(f(x1-1,y1,x2,y2,n,m,turns,UP)) return true;
 56              //向右走,弯折 
 57              else if(f(x1,y1+1,x2,y2,n,m,turns+1,RIGHT)) return true;
 58              //向左走,弯折 
 59              else if(f(x1,y1-1,x2,y2,n,m,turns+1,LEFT)) return true;
 60              //如果三个方向都不通,则返回false
 61              else return false;
 62         case RIGHT:      //当前是向右走 
 63              //下一步向上走,弯折 
 64              if(f(x1-1,y1,x2,y2,n,m,turns+1,UP)) return true;
 65              //向右走,同方向 
 66              else if(f(x1,y1+1,x2,y2,n,m,turns,RIGHT)) return true;
 67              //向下走,弯折 
 68              else if(f(x1+1,y1,x2,y2,n,m,turns+1,DOWN)) return true;
 69              //如果三个方向都不通,则返回false
 70              else return false;
 71         case DOWN:       //当前是向下走
 72              //下一步向右走,弯折 
 73              if(f(x1,y1+1,x2,y2,n,m,turns+1,RIGHT)) return true;
 74              //向下走,同方向 
 75              else if(f(x1+1,y1,x2,y2,n,m,turns,DOWN)) return true;
 76              //向左走,弯折 
 77              else if(f(x1,y1-1,x2,y2,n,m,turns+1,LEFT)) return true;
 78              //如果三个方向都不通,则返回false
 79              else return false;
 80         case LEFT:       //当前是向左走
 81              //下一步向上走,弯折 
 82              if(f(x1-1,y1,x2,y2,n,m,turns+1,UP)) return true;
 83              //向下走,弯折 
 84              else if(f(x1+1,y1,x2,y2,n,m,turns+1,DOWN)) return true;
 85              //向左走,同方向 
 86              else if(f(x1,y1-1,x2,y2,n,m,turns,LEFT)) return true;
 87              //如果三个方向都不通,则返回false
 88              else return false;
 89         case STAY:       //此时还没移动 
 90              //第一步向上走 
 91              if(f(x1-1,y1,x2,y2,n,m,turns,UP)) return true;
 92              //第一步向右走
 93              else if(f(x1,y1+1,x2,y2,n,m,turns,RIGHT)) return true;
 94              //第一步向下走 
 95              else if(f(x1+1,y1,x2,y2,n,m,turns,DOWN)) return true;
 96              //第一步向左走 
 97              else if(f(x1,y1-1,x2,y2,n,m,turns,LEFT)) return true;
 98              //如果四个方向都不通,则返回false
 99              else return false;
100     }
101 }

 

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
8259214 2013-05-08 11:09:12 Accepted 1175 5921MS 2412K 4541 B G++ freecode

 

Freecode : www.cnblogs.com/yym2013

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [hdu 1175:连连看(dfs 深度优先搜索)](http://www.yangyingming.com/article/346)**