连连看

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 41 2 3 40 0 0 04 3 2 141 1 3 41 1 2 41 1 3 32 1 2 43 40 1 4 30 2 4 10 0 0 021 1 2 41 3 2 30 0

Sample Output

YESNONONONOYES

---

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 
      
         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
       
        <=1000,0
        
         <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
         <50) 24         while(q--){     //循环q次，每次为一次询问 25             //输入本次询问的两点坐标 26             cin>>x1>>y1>>x2>>y2; 27             if(x1==x2 && y1==y2) {cout<<"NO"<
          
           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		5921MS	2412K		G++

 

Freecode :