HDU 2579 Dating with girls(2)_C/C++_编程开发_程序员俱乐部

#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 105

int 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;
}

• 
• 大小: 6.2 KB

• 查看图片附件