9517 Link Link Look
9517 Link Link Look
该题有题解
时间限制:2000MS 内存限制:65535K
提交次数:67 通过次数:18
题型: 编程题 语言: G++;GCC
Description
相信大家都玩过连连看.连看看是在一个方格上面有各种不同的图案,没图案的格子视为通道.如果能找到两个图案,他们之间能通过通道而转弯次数不超过2的道路连接起来,那么这两个图案视为可消图案
例如
10024
02057
33001
这样两个1,2,3都可消
但
10030
04070
06000
54321
这样的两个1是不可消的,但如果把3消去,两个1就可以消去了..
由于规则太复杂了,导致玩的时候我有点混乱,所以想请你帮我.现在我在一个局面卡住了,进行不下去.所以想请你帮我看看现在还有多少对可以消去的图案(注意不一定所有的图案都配对的)
例如
10024
02057
33001
就有3对
输入格式
第一行是两个数n,m表示方格大小为n*m (50>n,m>0)
接下来是n行,每一行有m个数,0表示空,其余数字表示对应的图案,图案数字类型不超过20
输出格式
输出一个数字表示当前局面可消对数(我可以有多少种选择)
看样例2
输入样例
Sample Input #1:
3 5
1 0 0 2 4
0 2 0 5 7
3 3 0 0 1
Sample Input #2:
1 4
1 1 1 1
输出样例
Sample Output #1:
3
Sample Output #2:
3
提示
方格四周是没东西的,连线不能超过方格,一超过就不知道去到什么异空间了(@_@)
注意Sample Input/Output用#1和#2。。。,并不是输入的部分,而是表示这是两组不同的数据。
即,你所需做的是读入一组数据,输出答案,然后就可以结束程序了。
来源
ick2
作者
a470086609
这题的解题思路就是用深度优先搜索。用个for将每个不为0的点都进行dfs,并且将每个dfs过的点用数组flag存储起来,防止遍历后面的点进行dfs时重复计数了这个地方。而在对一个起始点进行dfs前还要用到一个book数组,用来将dfs时能够与起始点进行消对的点i用book[i]标记好,防止起始点向别的方向搜索时如果回到这个点上而又重复计数。再具体的解释在代码注释中。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,sum=0; int map[55][55],flag[55][55],book[55][55],next[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; //next表示移动的四个方向 //flag用来标记已经消过的点,避免重复计数。book用来当前搜索中已走过的路,避免重走 // void dfs(int x,int y,int change,int dect,int ans)//change表示已转弯次数,dect为上一次移动时的方向 { int tx,ty; for(int i=0; i<4; i++) //枚举四个移动方向 { tx=x+next[i][0]; ty=y+next[i][1]; if(tx>=n||tx<0||ty>=m||ty<0) continue; if(!map[tx][ty])//如果是通路 { if(change<2) { if(dect!=i) dfs(tx,ty,change+1,i,ans); else dfs(tx,ty,change,i,ans); } else if(change==2) { if(dect!=i) continue; else dfs(tx,ty,change,i,ans); } } if(map[tx][ty]==ans)//如果找到了相同数字 { if(!flag[tx][ty])//如果是未曾标记过的 { if(!book[tx][ty])//如果是未曾消过的 { if(change==2&&i!=dect) continue; else { book[tx][ty]=1; sum++; } } } } } } int main() { int i,j; memset(map,0,sizeof(map)); memset(book,0,sizeof(book)); memset(flag,0,sizeof(flag)); scanf("%d%d",&n,&m); for(i=0; i<n; i++) for(j=0; j<m; j++) scanf("%d",&map[i][j]); // for(i=0; i<n; i++) { for(j=0; j<m; j++) { if(map[i][j]!=0) { flag[i][j]=1; dfs(i,j,-1,-1,map[i][j]);//因为刚开始在起始点时是没有原始方向的(在dfs函数里用i等 //于0 1 2 3来表示四个方向,故这里起始用为-1,在第一次进入dfs时从0开始枚举,同时转弯次数 //也会从-1变为0。 memset(book,0,sizeof(book));//这里记得要重新清0 } } } printf("%d ",sum); return 0; }
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击