2136.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2136 on 2006-04-08 at 20:33:48 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int RM = 32;
const int CM = 64;
const int DIR[][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, { 0, 0 } };

class Frogger {
private:
	bool vst[CM][RM][CM];
	char map[RM][CM];
	int n, m, fx, fy, lmt;
	int code(int x, int y, int step) const { return (x<<24) | (y<<18) | step; }
	bool legal(int x, int y) const { return x >= 0 && x < n && y >= 0 && y < m; }
	void push(queue<int>&, int, int, int);
	bool canGo(int, int, int) const;
public:
	void build();
	int jump();
};
void Frogger::build() {
	scanf("%d %d %d\n", &lmt, &n, &m); n += 2;
	int i; memset(vst, false, sizeof(vst));
	for(i = 0; i < n; i++) gets(map[i]);
	for(i = 0; i < m; i++)
		if(map[n-1][i] == 'F') fx = n-1, fy = i;
}
void Frogger::push(queue<int>& Q, int x, int y, int step) {
	if(vst[step%m][x][y]) return;
	Q.push(code(x, y, step)); vst[step%m][x][y] = true;
}
bool Frogger::canGo(int x, int y, int step) const {
	int cc = (n-x)&1 ? (y+step)%m : ((y-step)%m+m)%m;
	return map[x][cc] != 'X';
}
int Frogger::jump() {
	queue<int> Q;
	Q.push(code(fx, fy, 0)); vst[0][fx][fy] = true;
	while(!Q.empty()) {
		int p = Q.front(), i; Q.pop();
		int x = p>>24, y = (p>>18)&63, step = p&262143;
		for(i = 0; i < 5; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1], cs = step+1;
			if(!legal(cx, cy)) continue;
			else if(map[cx][cy] == 'G') return cs;
			else if(cs < lmt && canGo(cx, cy, cs)) push(Q, cx, cy, cs);
		}
	}
	return -1;
}

int main()
{
	int t, T;
	Frogger frog;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		frog.build();
		int turn = frog.jump();
		if(turn > 0) printf("The minimum number of turns is %d.\n", turn);
		else printf("The problem has no solution.\n");
	}
	
	return 0;
}