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
分享到:
相关推荐
本压缩包中的资源——"算法-连连看(HDU-1175)(包含源程序).pdf"很可能提供了一个关于如何用编程语言实现连连看算法的详细讲解,包括源代码示例。 连连看算法的实现主要分为以下几个步骤: 1. **游戏初始化**:...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
hdu1001解题报告
HDU1059的代码
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
hdu 1574 passed sorce
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
hdu2101AC代码
* 题目1175:连连看,涉及到图的最短路径算法。 * 题目1180:诡异的楼梯,涉及到图的单源最短路径概念。 7. 图的最小生成树:图的最小生成树算法、图的 Kruskal 算法等。 * 题目1195:Open the Lock,涉及到图的...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
hdu 1166线段树代码
标题"HDu1000—2169部分代码"可能指的是作者在HDU OJ上解决了一系列题目,从1000号题到2169号题的部分代码。这通常意味着这些代码是用于解决特定算法问题的,并且这些提交已经被平台验证为正确,成功地通过了所有...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...