首页 > 其他 > 详细

hdu1175连连看(剪枝)

时间:2021-03-28 13:03:24      阅读:23      评论:0      收藏:0      [点我收藏+]

题目描述:

连连看

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53936    Accepted Submission(s): 13670


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
思路:要通过0路径找到匹配点,大力搜是唯一的选择,记录路径上转折的次数与位置,从起点的四个方向搜就能得到结果
但是不得行,会TLE,考虑剪枝,我们从一个点到另一个点的转折次数有限,如果转折次数为0,而我们当前的方向又不能
到达终点,哪是不是可以直接丢弃掉呢,这就剪掉了大量的搜索树
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
int m, n;
int maze[maxn][maxn];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
bool vis[maxn][maxn];
bool check(int x, int y) {
    return x >= 1 && x <= m && y >= 1 && y <= n && !vis[x][y];
}
pair<int, int>s, e;
bool dfs(int x,int y,int pre,int last) {
    vis[x][y] = 1;
    if (last == 0 && (x != e.first && y != e.second)) {
        return false;
    }//剪枝,最后一次方向旋转后,判断终点与当前点是否在一个方向
    for (int d = 0; d < 4; d++) {
        int tx = x + dx[d];
        int ty = y + dy[d];
        if (check(tx, ty)) {
            if (maze[tx][ty] == 0) {
                if (d == pre) {
                    if (dfs(tx, ty, d, last))return true;
                }
                else if(last>0){
                    if (dfs(tx, ty, d, last - 1))return true;
                }
            }
            else if ((d == pre||last>0)&&tx==e.first&&ty==e.second) {return true;}
        }
    }
    return false;
}
int main() {
    //freopen("test.txt", "r", stdin);
    while (scanf("%d%d", &m, &n) && n) {
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &maze[i][j]);
            }
        }
        int k; scanf("%d", &k);
        while (k--) {
             scanf("%d%d%d%d", &s.first, &s.second, &e.first, &e.second);
             if (maze[s.first][s.second] != maze[e.first][e.second]) {
                 printf("NO\n"); continue;
             }
             bool f = 0;
             for (int d = 0; d < 4; d++) {//四个方向出发
                 memset(vis, 0, sizeof(vis));
                 if (dfs(s.first, s.second, d, 2)) {
                     f = 1; printf("YES\n"); break;
                 }
             }
             if(!f)printf("NO\n");
        }
    }
    return 0;
}

 

 

hdu1175连连看(剪枝)

原文:https://www.cnblogs.com/MYMYACMer/p/14588202.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!