转载

光搜之---光棍节约会女孩

Dating with girls(2)

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2644 Accepted Submission(s): 735

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. 光搜之---光棍节约会女孩

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.

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

题解：这道题，首先不能在原地等，自己从一开始就应该要知道，然后走过的路还可以走，所以可以直接对这个点对k的取余来标记就可以，自己从开始想的不能在原地wa就是没考虑可以重复走的问题，改成了可以在原地等，离真相越来越远。。。

代码：

1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<cmath>  5 #include<algorithm>  6 #include<queue>  7 #define AREA b.x<0||b.x>=r||b.y<0||b.y>=c  8 using namespace std;  9 const int INF=0x3f3f3f3f; 10 const int MAXN=110; 11 char map[MAXN][MAXN]; 12 int sec; 13 int r,c,k; 14 int vis[MAXN][MAXN][10]; 15 int disx[4]={0,0,1,-1}; 16 int disy[4]={1,-1,0,0}; 17 struct Node{ 18     int x,y; 19 }; 20 void bfs(int sx,int sy){ 21     Node a,b; 22     int t; 23     sec=0; 24     queue<Node>dl; 25     memset(vis,0,sizeof(vis)); 26     a.x=sx;a.y=sy; 27     vis[sx][sy][0]=1; 28     dl.push(a); 29     while(!dl.empty()){ 30         t=dl.size(); 31         sec++; 32         while(t--){ 33             a=dl.front(); 34             dl.pop(); 35             for(int i=0;i<4;i++){ 36                 b.x=a.x+disx[i];b.y=a.y+disy[i]; 37                 if(AREA)continue; 38                 if(vis[b.x][b.y][sec%k])continue; 39                 if(sec%k==0){ 40                     if(map[b.x][b.y]=='G'){ 41                         printf("%d/n",sec); 42                         return; 43                     } 44                     vis[b.x][b.y][sec%k]=1; 45                     dl.push(b); 46                 } 47                 else{ 48                 if(map[b.x][b.y]=='#'){ 49                         continue; 50                     } 51                     if(map[b.x][b.y]=='G'){ 52                         printf("%d/n",sec); 53                         return; 54                     } 55                     vis[b.x][b.y][sec%k]=1; 56                     dl.push(b); 57                 } 58             } 59         } 60     } 61     puts("Please give me another chance!"); 62 } 63 int main(){ 64     int T; 65     scanf("%d",&T); 66     while(T--){ 67         scanf("%d%d%d",&r,&c,&k); 68         int sx,sy,ex,ey; 69         for(int x=0;x<r;x++){ 70             scanf("%s",map[x]); 71             for(int y=0;y<c;y++){ 72                 if(map[x][y]=='Y')sx=x,sy=y; 73             } 74         } 75         bfs(sx,sy); 76     } 77     return 0; 78 }

正文到此结束