首页 > 代码库 > HDU2579--Dating with girls(2)--(DFS, 判重)
HDU2579--Dating with girls(2)--(DFS, 判重)
Dating with girls(2)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1418 Accepted Submission(s): 393
Problem Description
If you have solved the problem Dating with
girls(1).I think you can solve this problem too.This problem is also
about dating with girls. Now you are in a maze and the girl you want to
date with is also in the maze.If you can find
the girl, then you can date with the girl.Else the girl will date with
other boys. What a pity!
The Maze is very strange. There are many stones in the maze. The stone will disappear at time t if t is a multiple of k(2<= k <= 10), on the other time , stones will be still there.
There are only ‘.’ or ‘#’, ’Y’, ’G’ on the map of the maze. ’.’ indicates the blank which you can move on, ‘#’ indicates stones. ’Y’ indicates the your location. ‘G’ indicates the girl‘s location . There is only one ‘Y’ and one ‘G’. Every seconds you can move left, right, up or down.
The Maze is very strange. There are many stones in the maze. The stone will disappear at time t if t is a multiple of k(2<= k <= 10), on the other time , stones will be still there.
There are only ‘.’ or ‘#’, ’Y’, ’G’ on the map of the maze. ’.’ indicates the blank which you can move on, ‘#’ indicates stones. ’Y’ indicates the your location. ‘G’ indicates the girl‘s location . There is only one ‘Y’ and one ‘G’. Every seconds you can move left, right, up or down.
Input
The first line contain an integer T. Then T
cases followed. Each case begins with three integers r and c (1 <= r ,
c <= 100), and k(2 <=k <= 10).
The next r line is the map’s description.
The next r line is the map’s description.
Output
For each cases, if you can find the girl, output the least time in seconds, else output "Please give me another chance!".
Sample Input
1
6 6 2
...Y..
...#..
.#....
...#..
...#..
..#G#.
Sample Output
7
Source
HDU 2009-5 Programming Contest
Recommend
lcy
每秒移动一格, 只能上下左右移动
这道题是一个搜索的题目, 因为要求到达的最短时间, 用BFS会更好一些,
需要注意的一点是, 石头会在某个时间消失, 这样的话, 不仅在搜索时需要结合当前时间判断此地块是否有石头, 路径判重时也要注意
普通的搜索题目判重时是不能重复经过同一地块(会导致状态相同,从而重复搜索), 而这道题目中两个状态相同是指在同一地块的前提下, 距离下一次石头消失的时间相同. 因此需要用一个三维数组, vis[MAXN][MAXN][K_MAXN] 标记状态
代码:
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 using namespace std; 5 int n,m,k,sx,sy,ex,ey; 6 struct haha 7 { 8 int x, y, step; 9 }q,temp; 10 char map[111][111]; 11 int dir[4][2]={0,1,0,-1,1,0,-1,0}; 12 int vis[111][111][11]; 13 void BFS() 14 { 15 int i; 16 q.x=sx; 17 q.y=sy; 18 q.step=0; 19 queue<struct haha>que; 20 memset(vis,0,sizeof(vis)); 21 vis[sx][sy][0]=1; 22 que.push(q); 23 while(!que.empty()) 24 { 25 temp=que.front(); 26 que.pop(); 27 if(temp.x==ex&&temp.y==ey) 28 { 29 printf("%d\n",temp.step); 30 return ; 31 } 32 for(i=0;i<4;i++) 33 { 34 int xx,yy; 35 xx=temp.x+dir[i][0]; 36 yy=temp.y+dir[i][1]; 37 if(xx>=0&&xx<n&&yy>=0&&yy<m&&(map[xx][yy]!=‘#‘||(temp.step+1)%k==0)&&!vis[xx][yy][(temp.step+1)%k]) 38 { 39 q.step=temp.step+1; 40 q.x=xx; 41 q.y=yy; 42 vis[xx][yy][(temp.step+1)%k]=1; 43 que.push(q); 44 } 45 } 46 } 47 printf("Please give me another chance!\n"); 48 } 49 int main() 50 { 51 int i,j,cas; 52 scanf("%d",&cas); 53 while(cas--) 54 { 55 scanf("%d %d %d",&n,&m,&k); 56 for(i=0;i<n;i++) 57 { 58 scanf("%s",map[i]); 59 for(j=0;j<m;j++) 60 { 61 if(map[i][j]==‘Y‘) {sx=i;sy=j;} 62 else if(map[i][j]==‘G‘) {ex=i;ey=j;} 63 } 64 } 65 BFS(); 66 } 67 return 0; 68 }
HDU2579--Dating with girls(2)--(DFS, 判重)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。