连连看

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 7173    Accepted Submission(s): 1847

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

 

比较有意思的一道题，看到的第一眼我就想到了dfs，试着写了一下，就是超时~~~后来加了一个vis数组，把题ac了，但是运行时间到3900MS+,很郁闷~~在网上搜了别人的代码，看到一个剪枝，模仿了一下，果然牛X，直接降到了64MS~~

代码如下：

1 #include
       
          2 #include
        
           3 #include
         
            4 using namespace std;  5 int map[1005][1005], N, M, x1, x2, y1, y2, flag;  6 int dx[] = {-1, 1, 0, 0};  7 int dy[] = {
     0, 0, -1, 1};  8 int vis[1005][1005];  9 void dfs(int x, int y, int count, int dir) 10 {
     11     if(flag) 12         return; 13     if(count >= 3) 14         return; 15     if(x == x2 && y == y2) 16     {
     17         flag = 1; 18         return; 19     } 20     if(x < 0 || y < 0 || x >= N || y >= M || map[x][y] != 0 || vis[x][y]) 21         return; 22     if(count == 2) 23     {
     24         if(!(dir==0&&y2==y&&x2
          
           x||dir==2&&y2
           
            y&&x2==x)) 25             return; 26     }//很关键的剪枝，如果没有时间会达到3906MS或者超时~~ 27     vis[x][y] = 1; 28     for(int i = 0; i < 4; i++) 29     {
     30         if(i == dir) 31             dfs(x + dx[i], y + dy[i], count, dir); 32         else 33             dfs(x + dx[i], y + dy[i], count+1, i); 34     } 35     vis[x][y] = 0; 36 } 37 int main() 38 {
     39     int ornum; 40     while(scanf("%d%d", &N, &M) && (N || M)) 41     {
     42         for(int i = 0; i < N; i++) 43             for(int j = 0; j < M; j++) 44                 scanf("%d", &map[i][j]); 45         scanf("%d", &ornum); 46         while(ornum--) 47         {
     48             scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 49             x1--; x2--; y1--; y2--; 50             flag = 0; 51             if((x1 != x2 || y1 != y2) && map[x1][y1] == map[x2][y2] && map[x1][y1] != 0) 52             {
     53                 memset(vis, 0, sizeof(vis)); 54                 vis[x1][y1] = 1; 55                 for(i = 0; i < 4; i++) 56                     dfs(x1 + dx[i], y1 + dy[i], 0, i); 57             } 58             if(flag) 59                 printf("YES\n"); 60             else printf("NO\n"); 61         } 62     } 63     return 0; 64 }
           
          
         
        
       

还看到有人用bfs写的，很仰慕，也用bfs写了一下，但是一直过不了，看了好长时间没看出来哪错了，郁闷~~~

这是bfs ac的博文~~

我把我wa的bfs代码发上来，求指导~~

1 #include
        
           2 #include
         
            3 #include
          
             4 #include
           
              5 using namespace std;  6 typedef struct node  7 {
       8     int x, y;  9     int count; 10     int dir; 11 }State; 12 queue
            
              q; 13 State begin; 14 int map[1005][1005], N, M, x1, x2, y1, y2, flag; 15 int dx[] = {-1, 1, 0, 0}; 16 int dy[] = {
      0, 0, -1, 1}; 17 int vis[1005][1005]; 18 void bfs() 19 {
      20     q.push(begin); 21     vis[x1][y1] = 0; 22     while(!q.empty()) 23     {
      24         State u = q.front(); 25         q.pop(); 26         if(u.x == x2 && u.y == y2 && u.count <= 2) 27         {
      28             flag = 1; 29             return; 30         } 31         for(int i = 0; i < 4; i++) 32         {
      33             State v; 34             v.x = u.x + dx[i]; 35             v.y = u.y + dy[i]; 36             v.count = u.count; 37             v.dir = i; 38             if(v.x>=0&&v.x
             
              =0&&v.y
              
                2) 44 continue; 45 } 46 if(vis[v.x][v.y] >= v.count) 47 { 48 vis[v.x][v.y] = v.count; 49 q.push(v); 50 } 51 } 52 } 53 } 54 } 55 int main() 56 { 57 int ornum; 58 while(scanf("%d%d", &N, &M) && (N || M)) 59 { 60 for(int i = 0; i < N; i++) 61 for(int j = 0; j < M; j++) 62 scanf("%d", &map[i][j]); 63 scanf("%d", &ornum); 64 while(ornum--) 65 { 66 scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 67 x1--; x2--; y1--; y2--; 68 flag = 0; 69 if((x1 != x2 || y1 != y2) && map[x1][y1] == map[x2][y2] && map[x1][y1] != 0) 70 { 71 for(int i = 0; i < N; i++) 72 for(int j = 0; j < M; j++) 73 vis[i][j] = 4; 74 begin.x = x1; begin.y = y1; begin.count = -1; begin.dir = -1; 75 bfs(); 76 } 77 if(flag) 78 printf("YES\n"); 79 else printf("NO\n"); 80 while(!q.empty()) 81 q.pop(); 82 } 83 } 84 return 0; 85 }