1918.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1918
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int NMAX = 20+2;
const int MMAX = 50+2;
char path[NMAX][MMAX];
bool vis[MMAX][NMAX][MMAX];
int n,m,cas,tle;
int gx,gy;
int dir[5][2] = {{-1,0},{0,-1},{1,0},{0,1},{0,0}};
int cnt;
struct NODE {
	int x,y,time;
	NODE() {}
	NODE(int a,int b,int c) : x(a),y(b),time(c) {}
	void next_pos(int d) {
		x += dir[d][0];
		y += dir[d][1];
		time ++;
	}
	bool is_ok() {
		int i,j;
		if (x<0||y<0||x>=n||y>=m||time>tle||vis[time%m][x][y]) return false;
		if (x==n-1 || x==0) return true;
		i = (n-1) - x;
		if (i&1) j = (y-time) % m + m;
		else j = y+time;
		if (path[x][j%m] == 'X') return false;
		return true;
	}
	bool is_end() {
		if (path[x][y] == 'G') return true;
		return false;
	}
};
queue<NODE> sq;
int ans;
void bfs() {
	int i,j;
	NODE now,next;
	cnt = 1;
	while (!sq.empty()) {
		now = sq.front();
		sq.pop();
		if (now.time >= tle) return;
		for (i=0;i<5;i++) {
			next = now;
			next.next_pos(i);
			if (next.is_ok()) {
				if (next.is_end()) {
					ans = next.time;
					return;
				}
				vis[next.time%m][next.x][next.y] = true;
				sq.push(next);
				//printf("\b\b\b\b\b\b\b\b%8d",++cnt);
			}
		}
	}
}
int main() {
	int i,j;
	scanf("%d",&cas);
	while (cas --) {
		scanf("%d %d %d",&tle,&n,&m); getchar();
		n += 2;
		for (i=0;i<n;i++) gets(path[i]);
		while (!sq.empty()) sq.pop();
		memset(vis,0,sizeof(vis));
		for (i=0;i<m;i++) {
			if (path[n-1][i] == 'F') {
				sq.push(NODE(n-1,i,0));
				vis[0][n-1][i] = true;
			}
			if (path[0][i] == 'G') gx = 0, gy = i;
		}
		ans = -1;
		bfs();
		if (ans == -1) puts("The problem has no solution.");
		else printf("The minimum number of turns is %d.\n",ans);
	}
}