HDU 2579 Dating with girls(2)
KIDx 的解题报告
题意很简单：http://acm.hdu.edu.cn/showproblem.php?pid=2579
#include <iostream>#include <queue>using namespace std;#define inf 0x3fffffff#define M 105int r, c, mod, step[11][M][M];//step加维枚举余数所有状态int x_move[4] = {-1, 0, 1, 0};int y_move[4] = {0, 1, 0, -1};char map[M][M];struct pos{int x, y, z;};void bfs (){pos ft, tp;int i, j, k;for (i = 0; i < r; i++){for (j = 0; j < c; j++){for (k = 0; k < 11; k++)step[k][i][j] = inf; //初始化if (map[i][j] == 'Y')//起点ft.x = i, ft.y = j;}}ft.z = 0;step[ft.z][ft.x][ft.y] = 0;queue<pos> q;q.push (ft);while (!q.empty()){ft = q.front();q.pop();if (map[ft.x][ft.y] == 'G')//终点{printf ("%d\n", step[ft.z][ft.x][ft.y]);return ;}for (i = 0; i < 4; i++){tp.x = ft.x + x_move[i];tp.y = ft.y + y_move[i];tp.z = (ft.z+1) % mod;if (tp.x < 0 || tp.y < 0 || tp.x >= r || tp.y >= c)continue;if (map[tp.x][tp.y] == '#' && tp.z > 0)//余数是0才可以走到#continue;if (step[tp.z][tp.x][tp.y] <= step[ft.z][ft.x][ft.y] + 1)continue;//走过的状态就不用走了step[tp.z][tp.x][tp.y] = step[ft.z][ft.x][ft.y] + 1;q.push (tp);}}puts ("Please give me another chance!");}int main(){int t, i;scanf ("%d", &t);while (t--){scanf ("%d%d%d", &r, &c, &mod);for (i = 0; i < r; i++)scanf ("%s", map[i]);bfs();}return 0;}