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。用数字记录个个方向。方向改变就ans+1。最后判断即可。
AC:
#include<stdio.h> #include<string.h> int n,m,endx,endy,temp; int map[1005][1005],vis[1005][1005]; int dir[4][2]={-1,0,0,-1,1,0,0,1}; void dfs(int x,int y,int d,int ans) { vis[x][y]=1; if(temp||ans>2) return; if(endx==x&&endy==y&&ans<=2) temp=1; for(int i=0;i<4;i++) { int nx,ny; nx=x+dir[i][0]; ny=y+dir[i][1]; if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny]&&!map[nx][ny]) { if(d!=i) dfs(nx,ny,i,ans+1); else dfs(nx,ny,i,ans); vis[nx][ny]=0; } } } int main() { while(~scanf("%d%d",&n,&m)&&(n+m)) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); int t; scanf("%d",&t); while(t--) { int stax,stay; temp=0; scanf("%d%d%d%d",&stax,&stay,&endx,&endy); if(map[stax][stay]!=map[endx][endy]||!map[stax][stay]||!map[endx][endy]) { printf("NO\n"); continue; } map[endx][endy]=0; for(int i=0;i<4;i++) { int nx,ny; nx=stax+dir[i][0]; ny=stay+dir[i][1]; memset(vis,0,sizeof(vis)); if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!temp&&!map[nx][ny]&&!vis[nx][ny]) dfs(nx,ny,i,0); } if(temp) printf("YES\n"); else printf("NO\n"); map[endx][endy]=map[stax][stay]; } } return 0; }
总结:
1.思路正确但是写代码的方式不对,细节想不够仔细;
2.写代码思维有点混乱;
3.也用bfs写过,但是发现了记录每个点的转弯数最小值跟它的方向有关。
相关推荐
MFC连连看 MFC连连看 MFC连连看 MFC连连看 MFC连连看
微信小游戏源码 奇葩连连看游戏源码(仅用于学习参考)微信小游戏源码 奇葩连连看游戏源码(仅用于学习参考)微信小游戏源码 奇葩连连看游戏源码(仅用于学习参考)微信小游戏源码 奇葩连连看游戏源码(仅用于学习...
连连看-连连看.rar
好东西大家分享——JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看JAVA连连看
连连看寻路方法连连看寻路方法连连看寻路方法连连看寻路方法连连看寻路方法连连看寻路方法
用c++语言写的一个连连看,有源码,学习娱乐都可以。
连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看连连看...
连连看20合一的超级连连看20合一的超级连连看20合一的超级连连看
基于Android开发的连连看小游戏源码。 基于Android开发的连连看小游戏源码.基于Android开发的连连看小游戏源码.基于Android开发的连连看小游戏源码.基于Android开发的连连看小游戏源码.基于Android开发的连连看小...
cocoscreate开发的连连看项目
基于mfc开发的小游戏连连看源代码,有重新开始、重列、等级选择等功能
精品水晶连连看 精品水晶连连看. 精品水晶连连看 精品水晶连连看
android水果连连看游戏,可选难度、dfs判断是否匹配,计时器
在按键精灵中,用vbscript实现的一个模拟点击QQ连连看的测试代码
基于Java的连连看实现代码
小游戏(连连看)(连连看)小游戏(连连看)(连连看)小游戏(连连看)(连连看)
连连看游戏(c#)连连看游戏(c#)连连看游戏(c#)连连看游戏(c#)连连看游戏(c#)连连看游戏(c#)
涉及双缓冲和连连看算法....vc6.0实现
经典连连看小游戏,工程里包含了游戏面板、素材、算法代码,并且算法里有连线在最外侧的情况。可以直接运行,有任何问题欢迎交流
甘蔗连连看是甘蔗小游戏推出的一款连连看单机小游戏,这是非常风靡的办公室小游戏,甘蔗连连看游戏具有下面的特点: 1、由低到高的难度,让你循序渐进的成为连连看高手; 2、可以保存游戏进度,每日只需轻松的玩上一...