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)(包含源程序).rar
杭电ACMhdu1163
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
自己做的HDU ACM已经AC的题目
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
ACM HDU题目分类,我自己总结的大概只有十来个吧
Hdu 1237 解题代码