`

HDU 1175 连连看【2011年11月14号更新】

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=1175

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


有用剪枝:
如果走到当前位置已经转弯2次,若当前位置与目标位置既不同行也不同列,果断剪掉

速度还不错:


#include <iostream>
using namespace std;
#define inf 0x3fffffff
#define M 1001

int r, c, sx, sy, ex, ey, wan[M][M];
int map[M][M];
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
bool flag;

void dfs (int x, int y, int dir)
{
	if (x == ex && y == ey && wan[x][y] <= 2)
	{
		flag = true;
		return ;
	}
	if (wan[x][y] == 2 && x != ex && y != ey)    //剪枝
		return ;
	if (wan[x][y] > 2)    //剪枝
		return ;
	for (int i = 0; i < 4; i++)
	{
		int tx = x + x_move[i];
		int ty = y + y_move[i];
		if (tx < 0 || ty < 0 || tx >= r || ty >= c)
			continue;
		if ((tx != ex || ty != ey) && map[tx][ty] != 0 ||
         wan[tx][ty] < wan[x][y])
			continue;
		if (dir != -1 && dir != i && wan[tx][ty] < wan[x][y] + 1)
			continue;
		wan[tx][ty] = wan[x][y];
		if (dir != -1 && dir != i)
			wan[tx][ty]++;
		dfs (tx, ty, i);
		if (flag)
			return ;
	}
}

inline bool scan_d(int &num)      // 加速输入外挂,纯粹复制模板
{
        char in;
        bool IsN=false;
        in=getchar();
        if(in==EOF) return false;   
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}

int main()
{
	int i, j, q;
	while (~scanf ("%d%d", &r, &c), (r||c))
	{
		for (i = 0; i < r; i++)
			for (j = 0; j < c; j++)
				scan_d (map[i][j]);
		scan_d (q);
		while (q--)
		{
			scan_d (sx);
			scan_d (sy);
			scan_d (ex);
			scan_d (ey);
			sx--, sy--, ex--, ey--;
			if (map[sx][sy] == 0 || map[sx][sy] != map[ex][ey])
			{
				puts ("NO");
				continue;
			}
			for (i = 0; i < r; i++)
				for (j = 0; j < c; j++)
					wan[i][j] = inf;
			flag = false;
			wan[sx][sy] = 0;
			dfs (sx, sy, -1);
			if (flag)
				puts ("YES");
			else puts ("NO");
		}
	}
    return 0;
}
  • 大小: 6.1 KB
15
8
分享到:
评论

相关推荐

    算法-连连看(HDU-1175)(包含源程序).rar

    本压缩包中的资源——"算法-连连看(HDU-1175)(包含源程序).pdf"很可能提供了一个关于如何用编程语言实现连连看算法的详细讲解,包括源代码示例。 连连看算法的实现主要分为以下几个步骤: 1. **游戏初始化**:...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    hdu1001解题报告

    hdu1001解题报告

    HDU1059的代码

    HDU1059的代码

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    hdu2101解决方案

    hdu2101AC代码

    HDU图论题目分类

    * 题目1175:连连看,涉及到图的最短路径算法。 * 题目1180:诡异的楼梯,涉及到图的单源最短路径概念。 7. 图的最小生成树:图的最小生成树算法、图的 Kruskal 算法等。 * 题目1195:Open the Lock,涉及到图的...

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu acm1166线段树

    hdu 1166线段树代码

    Hdu1000—2169部分代码

    标题"HDu1000—2169部分代码"可能指的是作者在HDU OJ上解决了一系列题目,从1000号题到2169号题的部分代码。这通常意味着这些代码是用于解决特定算法问题的,并且这些提交已经被平台验证为正确,成功地通过了所有...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

Global site tag (gtag.js) - Google Analytics