#include <vector>
#include <queue>
#include <string>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
struct Node
{
	int x,y;
	int step;
};

int bfs(vector<string> &maze,int sx,int sy)
{
	int h=maze.size();
	int w=maze[0].size();
	vector<vector<int>> vis(h,vector<int>(w,0));
	queue<Node> q;
	Node n={sx,sy,0};
	q.push(n);
	vis[sx][sy]=1;

	//四个方向：右、下、左、上
	const int dx[]={0,1,0,-1};
	const int dy[]={1,0,-1,0};

	while(!q.empty())
	{
		Node now=q.front();
		q.pop();

		//检查是否到达终点
		if(maze[now.x][now.y]=='E')
		{
			return now.step;
		}

		//尝试四个方向
		for(int i=0;i<4;i++)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];

			//检查新位置是否有效
			if(nx>=0&&nx<h&&ny>=0&&ny<w&&(maze[nx][ny]=='*'||maze[nx][ny]=='E')&&!vis[nx][ny])
			{
				Node s={nx,ny,now.step+1};
				q.push(s);
				vis[nx...