hdu 2579 余数判重

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

7

思路写在注释上了

//这个题跟那个楼梯不一样 那个楼梯是在原地等待，而这个不能再原地等待，因为 这块石头过不去 可能其他地方的石头就能过去了。判重是根据余数来判重。 //当余数走道这个格子的余数想等的话就表示是同一状太 就没必要走了。 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> using namespace std; struct node { int x; int y; int step; }; char map[101][101]; int vis[101][101][10]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; int n ,m , k; int zx,zy,xx,yy; int ans; void bfs() { queue<node>q; node a={xx,yy,0}; vis[xx][yy][0]=1; q.push(a); while(!q.empty()) { a=q.front(); q.pop(); // printf("1 %d %d\n",a.x,a.y); if(a.x==zx&&a.y==zy) { ans=a.step; return ; } for(int i=0;i<4;i++) { int xx=dir[i][0]+a.x; int yy=dir[i][1]+a.y; if(xx>n||xx<1||yy>m||yy<1) continue; if(vis[xx][yy][(a.step+1)%k]) continue; if(map[xx][yy]=='#') { if((a.step+1)%k==0) { vis[xx][yy][(a.step+1)%k]=1; node b={xx,yy,(a.step+1)}; q.push(b); // printf("2 %d %d\n",xx,yy); }// } else { vis[xx][yy][(a.step+1)%k]=1; node b={xx,yy,a.step+1}; q.push(b); // printf("2 %d %d\n",xx,yy); } } } ans=-1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { scanf("%s",map[i]+1); for(int j=1;j<=m;j++) { if(map[i][j]=='Y'){ xx=i,yy=j;} if(map[i][j]=='G') zx=i,zy=j; } } memset(vis,0,sizeof(vis)); bfs(); if(ans!=-1) printf("%d\n",ans); else printf("Please give me another chance!\n"); } }