Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
7
Indexable
#include<iostream>
using namespace std;

int t,m,n;
bool checkbien(int x, int y)
{
	
	if (x<0 || x>m || y<0 || y>m) return false;
	return true;
}


char Map[500][500];


int D[400][400];
int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0};
char Qx[100000], Qy[100000];
int Qd[100000];
int rear = -1;
int front = -1;


void push(int x, int y,int d)
{
	rear ++;
	Qx[rear] = x;
	Qy[rear] = y;
	Qd[rear] = d;
}

void pop(int &x, int &y, int &d)
{
	front ++;
	x = Qx[front];
	y = Qy[front];
	d = Qd[front];
}

int BFS(int x, int y,int d)
{
	push(x,y,0);

		while (rear != front)
		{
			pop(x,y,d);
			for (int i=0; i<4; i++)
			{
				int xx = x+dx[i];
				int yy = y+dy[i];
				
				if (checkbien(xx,yy))
				{
					if (Map[xx][yy] == 'E')
					{
						push(xx,yy,d+1);
						Map[xx][yy] = 'S';
					}
					else if (Map[xx][yy] == 'B')
					{
						push(xx,yy,d+2);
						Map[xx][yy] = 'S';
					}
					else {if (Map[xx][yy] == 'T')
					{
						return d+1;
					} else return -1;
				}
			}
		}
	}
}

int main()
{
	freopen("input.txt","r",stdin);

	cin >> t;
	int tx,ty;
	int yx,yy;
	for (int tc=1; tc<=t; tc++)
	{
		cin >> m >> n;
		
		front = rear = -1;

		for (int i=0; i<m; i++) cin >> Map[i];	

		for (int i=0; i<m; i++)
		{
			for (int j=0; j<n; j++)
			{
				if (Map[i][j] == 'Y')
				{
					yx = i;
					yy = j;
				}
				else if (Map[i][j] = 'T')
				{
					tx = i;
					ty = j;
				}
			}
		}
		cout << "#" << tc << " " << BFS(yx,yy,0) << endl;
	}

	return 0;
}


Editor is loading...