589

#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>

#define ll long long
#define INF 100000000

using namespace std;


struct INFO{
	string str;
	int CNT;
	int BX;
	int BY;
	int SX;
	int SY;
};

int MX;
string input[25];
int tx,ty;
int r,c;
string path="";
const int dirx[4]={-1,0,0,1};
const int diry[4]={0,1,-1,0};
const char Dir[6] = {'N','E','W','S'};
const  char dir[6] = {'n','e','w','s'};
map<int,bool> vis[25][25][25][25];


struct cmp {
    bool operator() (INFO a, INFO b) {
		if(a.CNT!=b.CNT)
        return a.CNT > b.CNT;

        return a.str.size()>b.str.size();
    }
};

bool check(int x,int y)
{
	if(x < 0 || x >= r || y < 0 || y >= c || input[x][y]!='.')
		return 0;
	return 1;
}
void BFS(int cnt,int bx,int by,int sx,int sy)
{
	vis[sx][sy][bx][by][0]=1;
	priority_queue<INFO,vector<INFO>,cmp> q;

	INFO info;

	info.str = "";
	info.CNT = cnt;
	info.BX = bx;
	info.BY = by;
	info.SX = sx;
	info.SY = sy;

	int x ,y;
	int distance;
	int srcx,srcy;

	q.push(info);
	while(!q.empty())
	{
		info = q.top();
		q.pop();

		x = info.BX;
		y = info.BY;
		distance=info.CNT;
		srcx = info.SX;
		srcy = info.SY;

		if(x==tx && y==ty)
		{
			if(distance<MX)
			{
				MX = distance;
				path = info.str;
			}
			else if(distance==MX)
			{
				if(info.str.size()<path.size())
					path = info.str;
			}
			else
			break;
			continue;
		}

		for(int i=0;i<4;i++)
		{
			INFO pINFO = info;



			pINFO.SX += dirx[i];
			pINFO.SY += diry[i];

			if(check(pINFO.SX,pINFO.SY)==0)
			continue;
			pINFO.str.append(1u,dir[i]);//char(Dir[i]+32);
			if(pINFO.SX == pINFO.BX && pINFO.SY==pINFO.BY)
			{
				pINFO.BX +=dirx[i];
				pINFO.BY +=diry[i];
				if(check(pINFO.BX,pINFO.BY)==0)
				continue;
				pINFO.CNT +=1;
				if(pINFO.CNT>MX)
				continue;
				//pINFO.str.erase(pINFO.str.begin()+(pINFO.str.size()-2));
				//pINFO.str.append(1u,Dir[i]);
				pINFO.str[pINFO.str.size()-1] = Dir[i];
			}

			if(vis[pINFO.SX][pINFO.SY][pINFO.BX][pINFO.BY][path.size()])
			continue;
			else
			{
				vis[pINFO.SX][pINFO.SY][pINFO.BX][pINFO.BY][path.size()] = 1;
				q.push(pINFO);
			}
		}

	}

}


int main()
{
	int tt=1;
	int bx,by,sx,sy;

	while(cin>>r)
	{
		cin>>c;

		if(r+c==0)
		break;

		for(int i=0;i<r;i++)
		{
			cin>>input[i];
			for(int j=0;j<c;j++)
			{
				if(input[i][j]=='S')
				{
					sx = i;
					sy = j;
				}
				else if(input[i][j]=='T')
				{
					tx = i;
					ty = j;
				}
				else if(input[i][j]=='B')
				{
					bx = i;
					by = j;
				}
				if(input[i][j]!='#')
					input[i][j]='.';
				for(int m=0;m<r;m++)
					for(int n=0;n<c;n++)
						vis[i][j][m][n].clear();
			}
		}
		path = "";
		MX = INF;
		BFS(0,bx,by,sx,sy);
		if(path.size()==0)
		{
			cout<<"Maze #"<<tt++<<"\n";
			cout<<"Impossible.\n\n";
		}
		else
		{
			cout<<"Maze #"<<tt++<<"\n";
			cout<<path<<"\n\n";
		}
	}//while loop

	return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *