- 浏览: 121823 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
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的封装
Tempter of the Bone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26363 Accepted Submission(s): 7218
Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
题意:意思是在地图中S代表起始点,每个点只能停留1秒,便会沉落,而D代表门的所在,将在t秒后打开然后关闭,问狗是否能安全逃出迷宫
//剪枝:当格子数小于t时候,不必搜索
AC代码:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26363 Accepted Submission(s): 7218
Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
题意:意思是在地图中S代表起始点,每个点只能停留1秒,便会沉落,而D代表门的所在,将在t秒后打开然后关闭,问狗是否能安全逃出迷宫
//剪枝:当格子数小于t时候,不必搜索
AC代码:
#include <iostream> #include <queue> using namespace std; char map[8][8]; int visit[8][8]; int n, m, t; int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; typedef struct{ int x, y, t; }Block; Block s_n, e_n; bool dfs(Block temp) { int i, cnt; // cout<<"x = "<<temp.x<<" y = "<<temp.y<<" t="<<temp.t<<endl; if(map[temp.x][temp.y] == 'D' && temp.t == t) return true; cnt = (t - temp.t) - abs(temp.x - e_n.x) - abs(temp.y - e_n.y); if(cnt < 0 || cnt & 1) return false; for(i = 0; i < 4; i++) { Block cur; cur.x = temp.x + d[i][0]; cur.y = temp.y + d[i][1]; cur.t = temp.t + 1; if(cur.t > t) continue; if(cur.x >= 0 && cur.x < n && cur.y >=0 && cur.y < m && (map[cur.x][cur.y] == '.' || map[cur.x][cur.y] == 'D') && !visit[cur.x][cur.y]) { visit[cur.x][cur.y] = 1; if(dfs(cur)) return true; visit[cur.x][cur.y] = 0; } } return false; } int main() { int i, j, wall; while(cin>>n>>m>>t) { wall = 0; if(!n && !m && !t) break; for(i = 0; i < n; i++) for(j = 0; j < m; j++) { cin>>map[i][j]; if(map[i][j] == 'S') { s_n.x = i; s_n.y = j; }else if(map[i][j] == 'D') { e_n.x = i; e_n.y = j; }else if(map[i][j] == 'X') { wall++; } } if(n * m - wall < t) { cout<<"NO"<<endl; continue; } s_n.t = 0; 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 3122回溯法是设计递归过程的一种重要方法,它的求解过程是遍历一个状态 ... -
螺旋矩阵
2011-10-19 13:26 957给一个正整数n,输出一个n*n的螺旋矩阵 螺旋矩阵可以是逆时针 ... -
HDU2896(病毒侵袭)
2011-09-26 13:46 861病毒侵袭 Time Limit: 2000/1 ... -
HDU2060(Snooker)
2011-09-17 19:20 866Snooker 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 ... -
求一个集合的全排列
2011-09-11 14:49 776#include <iostream> usin ... -
HDU1175连连看
2011-09-09 23:24 753连连看 Time Limit: 20000/10000 MS ... -
HDU1711Number Sequence
2011-09-09 13:09 713Number 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 986Treasure the new start, freshme ... -
HDU2251Seinfeld
2011-08-24 13:39 877Seinfeld Time Limit: 2000/1000 ... -
HDU2083简易版之最短距离
2011-08-22 15:30 892简易版之最短距离 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 1010-2500解题报告,ACMer可以借鉴一下
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
ACM比赛解题报告,包括hdu1880、zoj1010、zoj1015,为原创的报告,算法不一定最优的
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases. In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100). Output For each test case, print ...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦