诡异的楼梯(bfs).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int dic[5][2] =
{ {0,0},{1,0},{-1,0},{0,1},{0,-1} };
int n,m,mmin;
int tx,ty;
char map[30][30];
bool hash[30][30][2];

struct inf {
	int x,y;
	int t;
	bool isok(int d)
	{
		x += dic[d][0];
		y += dic[d][1];
		
		if (x<0 || y<0 || x>=n || y>=m || map[x][y] == '*') {
			return false;
		}
		if (d == 0) {
			t ++;
			if (hash[x][y][t%2]) {
				return false;
			}
			return true;
		}
		if (d == 1 || d == 2) {//up, down
			if (map[x][y] == '|' && t%2) {//change
				return false;
			}
			else if (map[x][y] == '-' && t%2 ==0) {
				return false;
			}
		}
		else {//left, right
			if (map[x][y] == '-' && t%2) {//change
				return false;
			}
			else if (map[x][y] == '|' && t%2 ==0) {
				return false;
			}
		}
		if (map[x][y] == '|' || map[x][y] == '-') {
			x += dic[d][0];
			y += dic[d][1];
		}
		if (x<0 || y<0 || x>=n || y>=m || map[x][y] == '*') {
			return false;
		}
		t ++;
		if (hash[x][y][t%2]) {
			return false;
		}
		hash[x][y][t%2] = true;
		return true;
	}
};
queue<inf> SQ;

void bfs()
{
	inf now,t;
	int l,i;
	l = SQ.size();
	while (l--) {
		now = SQ.front();
		SQ.pop();
		if (now.x == tx && now.y == ty) {
			mmin = now.t;
			return ;
		}
		for (i=0;i<=4;i++) {
			t = now;
			if (t.isok(i)) {
				SQ.push(t);
			}
		}
		l = SQ.size();
	}
}

int main()
{
	int i,j;
	inf s;
	while (scanf("%d %d",&n,&m)==2) {
		getchar();
		memset(hash,false,sizeof(hash));
		for (i=0;i<n;i++) {
			gets(map[i]);
			for (j=0;j<m;j++) {
				if (map[i][j] == 'S') {
					s.x = i;
					s.y = j;
					s.t = 0;
					hash[i][j][0] = true;
				}
				else if (map[i][j] == 'T') {
					tx = i;
					ty = j;
				}
			}
		}//for
		int l = SQ.size();
		while (l--) {
			SQ.pop();
		}
		SQ.push(s);
		bfs();
		printf("%d\n",mmin);
	}
}