- 浏览: 121832 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
leelege:
让一切GenericDao都去死吧
自己写的一个Hibernate CURD的封装 -
liuxuejin:
不用泛型的飘过,个人觉得没有什么必要,因为增删查的代码(简单的 ...
自己写的一个Hibernate CURD的封装 -
java113096:
finallygo 写道icanfly 写道ricoyu 写道 ...
自己写的一个Hibernate CURD的封装 -
jiluo093:
http://jiluo093.iteye.com/blog/ ...
自己写的一个Hibernate CURD的封装 -
piao_bo_yi:
Dev|il 写道yin_bp 写道Dev|il 写道dnst ...
自己写的一个Hibernate CURD的封装
连连看
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6496 Accepted Submission(s): 1660
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
dfs过的代码,dfs太慢了
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6496 Accepted Submission(s): 1660
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
#include <iostream> #include <queue> using namespace std; const int MAX = 1005; int map[MAX][MAX]; int visit[MAX][MAX]; typedef struct{ int x, y, d, c; }Node; int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int m, n; Node s_n, e_n; bool bfs() { int i; queue<Node> q; q.push(s_n); visit[s_n.x][s_n.y] = 0; while(!q.empty()) { Node t = q.front(); q.pop(); // cout<<"x="<<t.x<<" y="<<t.y<<" c="<<t.c<<" flag="<<visit[t.x][t.y]<<endl; if(t.x == e_n.x && t.y == e_n.y && t.c <= 2) return true; for(i = 0; i < 4; i++) { Node cur; cur.x = t.x + d[i][0]; cur.y = t.y + d[i][1]; cur.d = i; cur.c = t.c; if(cur.x >= 0 && cur.y >=0 && cur.x < n && cur.y < m && (cur.x == e_n.x && cur.y == e_n.y || map[cur.x][cur.y] == 0) && !visit[cur.x][cur.y]) { if(cur.d != t.d) { cur.c = t.c + 1; if(cur.c > 2) continue; } q.push(cur); } } visit[t.x][t.y] = 1; } return false; } int main() { int i, j, q; while(cin>>n>>m) { if(!n && !m) break; for(i = 0; i < n; i++) for(j = 0; j < m; j++) cin>>map[i][j]; cin>>q; while(q--) { cin>>s_n.x>>s_n.y>>e_n.x>>e_n.y; s_n.x--; s_n.y--; e_n.x--; e_n.y--; s_n.c = -1; s_n.d = -1; if(s_n.x == e_n.x && s_n.y == e_n.y || map[s_n.x][s_n.y] != map[e_n.x][e_n.y] || !map[e_n.x][e_n.y]) { cout<<"NO"<<endl; continue; } memset(visit, 0, sizeof(visit)); if(bfs()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; }
dfs过的代码,dfs太慢了
#include <iostream> #include <queue> using namespace std; const int MAX = 1005; int map[MAX][MAX]; int visit[MAX][MAX]; typedef struct{ int x, y, d, c; }Node; int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int m, n; Node s_n, e_n; bool dfs(Node t) { if(t.x == e_n.x && t.y == e_n.y && t.c <= 2) return true; for(int i = 0; i < 4; i++) { Node cur; cur.x = t.x + d[i][0]; cur.y = t.y + d[i][1]; cur.d = i; cur.c = t.c; if(cur.x >= 0 && cur.y >=0 && cur.x < n && cur.y < m && (cur.x == e_n.x && cur.y == e_n.y || map[cur.x][cur.y] == 0) && !visit[cur.x][cur.y]) { if(cur.d != t.d) { cur.c = t.c + 1; if(cur.c > 2) continue; } visit[cur.x][cur.y] = 1; //做标识 if(dfs(cur)) return true; visit[cur.x][cur.y] = 0; //回溯消除标识 } } return false; } int main() { int i, j, q; while(cin>>n>>m) { if(!n && !m) break; for(i = 0; i < n; i++) for(j = 0; j < m; j++) cin>>map[i][j]; cin>>q; while(q--) { cin>>s_n.x>>s_n.y>>e_n.x>>e_n.y; s_n.x--; s_n.y--; e_n.x--; e_n.y--; s_n.c = -1; s_n.d = -1; if(s_n.x == e_n.x && s_n.y == e_n.y || map[s_n.x][s_n.y] != map[e_n.x][e_n.y] || !map[e_n.x][e_n.y]) { cout<<"NO"<<endl; continue; } memset(visit, 0, sizeof(visit)); if(dfs(s_n)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; }
发表评论
-
求n个元素集合的子集(幂集)或n个元素的组合
2011-10-21 13:19 3123回溯法是设计递归过程的一种重要方法,它的求解过程是遍历一个状态 ... -
螺旋矩阵
2011-10-19 13:26 957给一个正整数n,输出一个n*n的螺旋矩阵 螺旋矩阵可以是逆时针 ... -
HDU2896(病毒侵袭)
2011-09-26 13:46 862病毒侵袭 Time Limit: 2000/1 ... -
HDU2060(Snooker)
2011-09-17 19:20 867Snooker Time Limit: 1000/1000 M ... -
HDU1166(敌兵布阵)
2011-09-17 12:55 803敌兵布阵 Time Limit: 2000/1000 MS ( ... -
HDU1754 I Hate It
2011-09-16 23:40 1024参考资料:http://www.cppblog.com/MiY ... -
HDU1686Oulipo
2011-09-14 22:15 805Oulipo Time Limit: 3000/1000 MS ... -
HDU2100Lovekey
2011-09-12 17:16 691Lovekey Time Limit: 3000/1000 M ... -
HDU3368 Reversi(黑白棋)
2011-09-11 23:04 1029Reversi Time Limit: 5000/2000 M ... -
HDU1010Tempter of the Bone
2011-09-11 23:02 525Tempter of the Bone Time Limit: ... -
求一个集合的全排列
2011-09-11 14:49 776#include <iostream> usin ... -
HDU1711Number Sequence
2011-09-09 13:09 714Number Sequence Time Limit: 100 ... -
HDU1097A hard puzzle
2011-09-06 22:46 820A hard puzzle Time Limit: 2000/ ... -
HDU1004Let the Balloon Rise
2011-09-06 09:44 510Let the Balloon Rise Time Limit ... -
HDU2061Treasure the new start, freshmen!
2011-08-24 14:06 987Treasure the new start, freshme ... -
HDU2251Seinfeld
2011-08-24 13:39 877Seinfeld Time Limit: 2000/1000 ... -
HDU2083简易版之最短距离
2011-08-22 15:30 893简易版之最短距离 Time Limit: 1000/1000 ... -
HDU2093考试排名
2011-08-12 09:58 840考试排名 Time Limit: 1000/1 ... -
HDU2057A + B Again
2011-08-12 00:09 890A + B Again Time Limit: 1000/10 ... -
HDU2068RPG的错排
2011-08-10 22:45 729RPG的错排 Time Limit: 1000/1000 MS ...
相关推荐
算法-连连看(HDU-1175)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
语言:中文 (简体) 身在杭电必用的Chrome插件! HDU-GO是一款适用于杭州电子科技大学选课系统的Chrome拓展程序,具有自动抢课、自动学评教、自动计算学分功能。
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
自己做的HDU ACM已经AC的题目
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码