对称飞行器

分层图最短路

• 我们将每个点拆成六个点 : [x, y, k]表示从源点出发走到[x, y]点且使用了k次飞行器的最小步数(0 <= k <= 5)。
• 每一个点可扩展的点有五个, 分别是四领域和其中心对称点
• 考虑到每条边的边权均为1, 因此采用BFS算法实现该分层图最短路

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
using PII = pair<int, int>;
using PPI = pair<PII, int>;
const int N = 510, K = 6, INF = 0x3f3f3f3f;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int dist[N][N][K];
char g[N][N];

void solve(){
    memset(dist, 0x3f, sizeof dist);
    int n, m;
    cin >> n >> m;
    PII st, ed;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            cin >> g[i][j];
            if (g[i][j] == 'S')
                st = {i, j};
            if (g[i][j] == 'E')
                ed = {i, j};
        }
    // cout << st.x << ' ' << st.y << ' ' << ed.x << ' ' << ed.y << endl;
    queue<PPI> qu;
    dist[st.x][st.y][0] = 0;
    qu.push({{st.x, st.y}, 0});

    auto check = [&] (int nx, int ny) -> bool {
        return nx >= 1 and nx <= n and ny >= 1 and ny <= m;
    };

    while (qu.size()) {
        auto t = qu.front();
        qu.pop();
        int x = t.x.x, y = t.x.y, k = t.y;
        for (int i = 0; i < 4; i ++ ) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny) and g[nx][ny] != '#' and dist[nx][ny][k] == INF) {
                dist[nx][ny][k] = dist[x][y][k] + 1;
                qu.push({{nx, ny}, k});
            }
        }
        int tx = n + 1 - x, ty = m + 1 - y;
        if (check(tx, ty) and g[tx][ty] != '#' and k + 1 <= 5 and dist[tx][ty][k + 1] == INF) {
            dist[tx][ty][k + 1] = dist[x][y][k] + 1;
            qu.push({{tx, ty}, k + 1});
        }
    }

    int ans = INF;
    for (int i = 0; i <= 5; i ++ )
        ans = min(ans, dist[ed.x][ed.y][i]);
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t -- )
        solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct Node{
    int x; // 坐标 x
    int y; // 坐标 y
    int t; // 对称飞行器剩余次数
    int s; // 步数
};

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

vector<string> board;
vector<vector<int>> vis;
int M, N;

bool check(Node node) {
    return node.x >= 0 && node.x < N && node.y >= 0 && node.y < M
            && board[node.x][node.y] != '#' && vis[node.x][node.y] == 0;
}

int bfs(Node node) {
    queue<Node> q;
    q.push(node);
    
    while(!q.empty()) {
        Node n = q.front();
        q.pop();
        int x = n.x, y = n.y;
        if(board[x][y] == 'E') {
            return n.s;
        }
        for(int i = 0; i < 5; ++i) {
            Node temp;
            if(i == 4) {
                if(n.t > 0) {
                    // 这里下标从 0 开始，题目中下标从 1 开始
                    temp.x = N - 1 - x;
                    temp.y = M - 1 - y;
                    temp.s = n.s + 1;
                    temp.t = n.t - 1;
                }
            } else {
                temp.x = x + dx[i];
                temp.y = y + dy[i];
                temp.s = n.s + 1;
                temp.t = n.t;
            }
            
            if(check(temp)) {
                vis[temp.x][temp.y] = 1;
                q.push(temp);
            }
        }
    }
    
    return -1;
}

int main() {
    cin >> N >> M;
    board = vector<string>(N);
    vis = vector<vector<int>>(N, vector<int>(M));
    for(int i = 0; i < N; ++i) {
        cin >> board[i];
    }
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < M; ++j) {
            if(board[i][j] == 'S') {
                vis[i][j] = 1;
                Node node = {i, j, 5, 0};
                cout << bfs(node) << endl;
                return 0;
            }
        }
    }
}

三维广度搜索+位运算优化时间和空间

    这道题我们先分析一下，如果没有对称飞行器，就是一道普通广搜题。但是加了飞行器，如果飞行次数没有限制，也是一道普通广搜题只是除了四个direction多了一个分支。可是飞行器有次数限制。那么如果用(x,y)点的状态应该再加一个维度：飞行次数z。因为当z1不等于z2时，P(x,y,z1)和Q(x,y,z2)是两种不同的状态。

    假设z1<z2，即P和Q在相同的横纵坐标，但是P剩余的飞行次数更多。level1是P已经走的步数， level2是Q走的步数。如果level1<level2。假设从(x,y,z2)走到终点的最优解是n步，容易想到，从(x,y,z1)一定可以走n步到达终点。此时P状态走到最优点的步数更少。所以在层次遍历的最优解中不该包含z2.

    也就是说在向z增加转移的过程中，我们应该看matrix[x][y][0]...matrix[x][y][z]中是否已经有为1的点，如果有就不必再在第z层再走x，y。

    我们可以用位运算压缩三维数组，matrix[x][y]第z位代表是否已经遍历过(x,y,z)点。至于判断该点是否可走，我们应该看当前位置(x，y)小于等于z的位是否有1。类似于子网掩码的算法。高于z为置0，低位置1，与matrix[x][y]相与。得到结果大于0则说明有1不需遍历。等于0说明使用更少的飞行器没有走过这一点。可以加入遍历集。

代码：

package main

import (

   "fmt"

)



type Obj struct {

   X, Y, Z int

}

func main() {

   var n, m, sx, ex, sy, ey int

   var cur byte

   fmt.Scan(&n, &m)

   matrix := make([][]int, 0, n)

   for i := 0; i < n; i++ {

      matrix = append(matrix, make([]int, m))

      for j := 0; j < m + 1; j++ {

         fmt.Scanf("%c", &cur)

         switch cur {

         case 'S':

            sx = i

            sy = j

         case 'E':

            ex = i

            ey = j

         case '#':

            matrix[i][j] = 1

         }

      }

   }



   fmt.Println(bfs(sx,sy, ex, ey, n, m, matrix))

}



func bfs(sx, sy, ex, ey, n, m int, matrix [][]int) int {

   var direction = [][]int{{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, 1}}

   queue := make([]Obj, 1, m*n)

   queue[0] = Obj{sx, sy, 0}

   level := 0

   for len(queue) != 0 {

      level++

      for limit := len(queue); limit > 0; limit-- {

         node := queue[0]

         queue = queue[1:]

         direction[4][0], direction[4][1] = n-1-2*node.X, m-1-2*node.Y

         for _, d := range direction {

            x, y, z := node.X + d[0], node.Y + d[1], node.Z + d[2]

            if x == ex && y == ey {

               return level

            }

            if x >= 0 && y >= 0 && x < n && y < n && z <= 5 && ((1<<(z+1))-1) & matrix[x][y] == 0 {

               matrix[x][y] += 1 << z

               queue = append(queue, Obj{x, y, z})

            }

         }

      }

   }

   return -1

}

import java.util.*;

public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[][][] dp;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] tmp = line.split(" ");
        int m = Integer.parseInt(tmp[0]);
        int n = Integer.parseInt(tmp[1]);
        char[][] map = new char[m][n];
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for (int i = 0; i < m; i++) {
            line = scanner.nextLine();
            for (int j = 0; j < n; j++) {
                char ch = line.charAt(j);
                map[i][j] = ch;
                if (ch == 'S') {
                    sx = i;
                    sy = j;
                }
                if (ch == 'E') {
                    ex = i;
                    ey = j;
                }
            }
        }
        
        bfs(map, sx, sy, ex, ey);
        for (int i = 0; i < 6; i++) {
            if (dp[ex][ey][i] != 0) {
                System.out.println(dp[ex][ey][i]);
                return;
            }
        }
        System.out.println(-1);
    }
    
    public static void bfs(char[][] map, int sx, int sy, int ex, int ey) {
        Deque<int[]> queue = new ArrayDeque<>();
        int m = map.length;
        int n = map[0].length;
        dp = new int[m][n][6];
        
        queue.offerFirst(new int[] {sx, sy, 0});
        while (!queue.isEmpty()) {
            int[] status = queue.pollLast();
            int x = status[0], y = status[1], t = status[2];
            int nx = 0, ny = 0, nt = 0;
            for (int i = 0; i < 5; i++) {
                if (i == 4) {
                    nx = m - 1 - x;
                    ny = n - 1 - y;
                    nt = t + 1;
                } else {
                    nx = x + dx[i];
                    ny = y + dy[i];
                    nt = t;
                }
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && nt < 6 && map[nx][ny] != '#' && dp[nx][ny][nt] == 0) {
                    dp[nx][ny][nt] = dp[x][y][t] + 1;
                    if (nx == ex && ny == ey) {
                        return;
                    }
                    queue.offerFirst(new int[] {nx, ny, nt});
                }
            }
        }
    }
}

m, n = map(int, input().split())
tag = [[[1]*6 for _ in range(n)] for _ in range(m)]
M = []
for i in range(m):
    row = [_ for _ in input()]
    M.append(row)
    for index, r in enumerate(row):
        if 'S' == r:
            S = (i, index, 0)
        if 'E' == r:
            E = (i, index)
def getadj(i, j, z):
    adjs = []
    if z < 5 and m-1-i >= 0 and m-1-i < m and n-1-j>= 0 and n-1-j< n and tag[m-1-i][n-1-j][z+1] and M[m-1-i][n-1-j] != '#':
        tag[n-1-i][m-1-j][z+1] = 0
        adjs.append((n-1-i, m-1-j, z + 1))
    if i > 0 and tag[i - 1][j][z] and M[i - 1][j] != '#':
        tag[i - 1][j][z] = 0
        adjs.append((i-1, j, z))
    if i + 1 < m and tag[i + 1][j][z] and M[i + 1][j] != '#':
        tag[i + 1][j][z] = 0
        adjs.append((i + 1, j, z))
    if j > 0 and tag[i][j - 1][z] and M[i][j - 1] != '#':
        tag[i][j - 1][z] = 0
        adjs.append((i, j - 1, z))
    if j + 1 < n and tag[i][j + 1][z] and M[i][j + 1] != '#':
        tag[i][j + 1][z] = 0
        adjs.append((i, j + 1, z))
    return adjs
s1 = [S]
c = 0
#dfs
while(s1):
    s2 = []
    for i, j, z in s1:
        if (i, j) == E:
            print(c)
            exit()
        s2 += getadj(i, j, z)
    s1 = s2
    c += 1
print(-1)

#include <iostream>
#include <array>
#include <vector>
#include <set>
using namespace std;
/*
    看到大家都在把图看成多层图，然后用bfs。然而我比较笨，所以只能把dijkstra改了一下。

    模仿dijkstra算法，只不过每个点处维护的不只是一个距离，而是6个，
    分别代表到达该点时剩余不低于0，1，2，3，4，5次飞行次数时，所需的最小时间，记作rest_flight[0~5]，显然rest_flight是不降的。
    首次运行dijkstra算法，不进行任何飞行，只计算出每个点的rest_flight[5]。
    第二次运行dijkstra算法，至多进行一次飞行，一个点的rest_flight[4]
                                        1、或者是它的对称点的rest_flight[5]+1
                                        2、或者是已经经过的点集中点的rest_flight[4]+1
    ......
    需要注意的是，向周边节点集添加点时，如果可以优化飞点处时间，则要把飞点添加进去，而不能只添加上下左右，因为有些点只能飞到，不能走到。
*/

const int BIG = 1e7;

class node{
public:
    bool visited=false;
    array<int,7> rest_flight{BIG,BIG,BIG,BIG,BIG,BIG,BIG};
    enum TYPE {
        PATH,
        WALL,
        START,
        END
    } type;
    node(TYPE t=PATH):type(t){}
};

vector<vector<node>> map;
int m,n;
int start_row,start_col;
int end_row,end_col;

class pos{
public:
    int r,c;
    pos(int row,int col):r(row),c(col){}
};

class comp{
public:
    static int N;
    bool operator()(const pos &a,const pos &b)const{
        if(map[a.r][a.c].rest_flight[N]<map[b.r][b.c].rest_flight[N])
            return true;
        else if(map[a.r][a.c].rest_flight[N]==map[b.r][b.c].rest_flight[N]){
            if(a.r<b.r||a.r==b.r&&a.c<b.c)
                return true;
        }
        return false;
    }
};
int comp::N = 0;

vector<pos> delta{{-1,0},{1,0},{0,-1},{0,1}};

bool is_valid(const pos &p){
    return 0<=p.r&&p.r<n&&0<=p.c&p.c<m&&map[p.r][p.c].type!=node::WALL;
}

pos mirror(const pos &p){
    return {n-1-p.r,m-1-p.c};
}

node & getNode(const pos &p){
    return map[p.r][p.c];
}

void clean_up_visit(){
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            map[i][j].visited = false;
}

void dijkstra(int round){
    comp::N = round;
    set<pos,comp> prior_q; 
    map[start_row][start_col].rest_flight[round] = map[start_row][start_col].rest_flight[round+1] = 0;
    prior_q.emplace(start_row,start_col);
    while(!prior_q.empty()){
        auto it = prior_q.begin();
        if(getNode(*it).visited){
            prior_q.erase(it);
            continue;
        }
        getNode(*it).visited = true;

        if(is_valid(mirror(*it))) { // 如有必要，则添加飞点
            node &fly = getNode(mirror(*it));
            if(!fly.visited&&fly.rest_flight[round]> getNode(*it).rest_flight[round+1]+1){
                fly.rest_flight[round] = getNode(*it).rest_flight[round+1]+1;
                prior_q.insert(mirror(*it));
            }
        }

        for(const pos& d:delta){
            pos nxt_pos{it->r+d.r,it->c+d.c};
            if(!is_valid(nxt_pos)||getNode(nxt_pos).visited)
                continue;
            int mn = BIG;
            if(is_valid(mirror(nxt_pos)))
                mn = getNode(mirror(nxt_pos)).rest_flight[round + 1] + 1;
            if(mn > getNode(*it).rest_flight[round] +1)
                mn = getNode(*it).rest_flight[round] +1;
            if(mn < getNode(nxt_pos).rest_flight[round]){
                getNode(nxt_pos).rest_flight[round]=mn;
                prior_q.insert(nxt_pos);
            }
        }
        prior_q.erase(it);
    }
}

void print(){
    for(int i=5;i>=0;i--){
        cout<<"round "<<i<<endl;
        for(int r=0;r<n;r++) {
            for (int c = 0; c < m; c++)
                cout << map[r][c].rest_flight[i] << "\t";
            cout << endl;
        }
        cout<<endl;
    }
}

int main() {
    cin>>n>>m;
    map.resize(n,vector<node>(m));

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            char tmp;
            cin>>tmp;
            switch (tmp) {
                case '#': map[i][j].type = node::WALL; break;
                case 'S': map[i][j].type = node::START;
                    start_row=i,start_col=j;
                    break;
                case 'E': map[i][j].type = node::END;
                    end_row=i,end_col=j;
                    break;
                case '.': map[i][j].type = node::PATH; break;
            }
        }

    for(int i=5;i>=0;i--) {
        clean_up_visit();
        dijkstra(i);
    }

    // print();
    cout<<((map[end_row][end_col].rest_flight[0]==BIG)?-1:(map[end_row][end_col].rest_flight[0]));
}
// 64 位输出请用 printf("%lld")

import sys

n,m =[int(i) for i in sys.stdin.readline().split()]

data = []
for line in sys.stdin:
    a = list(line.strip("\n"))
    data.append(a)

def bfs(data, start, end,n,m,path):
    max_op = 5
    wait_to_visit = [[0,start[0],start[1],0]]
    while wait_to_visit:
        node_cur = wait_to_visit.pop(0)
        deepth_cur = node_cur[0]; op_cur = node_cur[3]
        x_cur, y_cur = node_cur[1], node_cur[2]
        path[x_cur][y_cur] = deepth_cur
        if op_cur < max_op:
            x_next = n-1-x_cur; y_next = m-1-y_cur
            if data[x_next][y_next] == "E":
                return deepth_cur+1
            if data[x_next][y_next] == "." and path[x_next][y_next]<0:
                wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur+1])
        if x_cur-1 > 0:
            x_next = x_cur-1; y_next = y_cur
            if data[x_next][y_next] == "E":
                return deepth_cur+1
            if data[x_next][y_next] == "." and path[x_next][y_next]<0:
                wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur])
        if x_cur+1 < n:
            x_next = x_cur+1; y_next = y_cur
            if data[x_next][y_next] == "E":
                return deepth_cur+1
            if data[x_next][y_next] == "." and path[x_next][y_next]<0:
                wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur])
        if y_cur-1 > 0:
            x_next = x_cur; y_next = y_cur-1
            if data[x_next][y_next] == "E":
                return deepth_cur+1
            if data[x_next][y_next] == "." and path[x_next][y_next]<0:
                wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur])

        if y_cur+1 < m:
            x_next = x_cur; y_next = y_cur+1
            if data[x_next][y_next] == "E":
                return deepth_cur+1
            if data[x_next][y_next] == "." and path[x_next][y_next]<0:
                wait_to_visit.append([deepth_cur+1,x_next,y_next,op_cur])
        #print(wait_to_visit)
    return -1     


def find(data, signal):
    for i in range(n):
        for j in range(m):
            if data[i][j] == signal:
                return i,j

path = [[-1]*m for _  in range(n)]
start = find(data, "S")
end = find(data, "E")
print(bfs(data, start,end,n,m,path))

//感谢楼上的大佬们不吝赐教，学到了很多东西。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] board = new char[n][m];
        for(int i=0;i<n;i++){
            String s = sc.next();
            board[i] = s.toCharArray();
        }
        int[][] visited = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]=='S'){
                    visited[i][j]=1;
                    Node node  = new Node(i,j,5,0);
                    System.out.println(bfs(node,board,visited));
                }
            }
        }
    }
    public static int bfs(Node start,char[][] board,int[][] vis){
        int n = board.length;
        int m = board[0].length;
        //四种走向的表示
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        Queue<Node> q = new LinkedList<>();
        q.offer(start);
        while(!q.isEmpty()){
            Node node = q.poll();
            int x = node.x;
            int y = node.y;
            if(board[x][y] == 'E'){
                return node.s;
            }
            //四个走向+使用飞行器（共五种情况）
            for(int i=0;i<5;i++){
                Node temp = new Node();
                if(i==4){
                    if(node.t>0){
                        // 这里下标从 0 开始，题目中下标从 1 开始
                        temp.x = n-1-x;
                        temp.y = n-1-y;
                        temp.t = node.t-1;
                        temp.s = node.s+1;
                    }
                }
                else {
                    temp.x = x+dx[i];
                    temp.y = y+dy[i];
                    temp.s = node.s+1;
                    temp.t = node.t;
                }
                if(check(temp,n,m,board,vis)){
                    vis[temp.x][temp.y] = 1;
                    q.offer(temp);
                }
            }
        }
        return -1;
    }
    public static boolean check(Node node,int n,int m,char[][] board,int[][] vis){
        return node.x>=0&&node.x<n&&node.y>=0&&node.y<m&&board[node.x][node.y]!='#'&&vis[node.x][node.y]==0;
    }
    public static class Node{
        int x;//坐标x
        int y;//坐标y
        int t;//飞行器的个数
        int s;//已经走的步数

        public Node() {
        }

        public Node(int x, int y, int t, int s) {
            this.x = x;
            this.y = y;
            this.t = t;
            this.s = s;
        }
    }
}

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Node struct {
	x    int
	y    int
	step int
	k    int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	m, _ := strconv.Atoi(scanner.Text())
	grid := make([][]string, 0)
	for i := 0; i < n; i++ {
		scanner.Scan()
		s := scanner.Text()
		ss := strings.Split(s, "")
		grid = append(grid, ss)
	}
	start := [2]int{}
	end := [2]int{}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == "S" {
				start[0] = i
				start[1] = j
			} else if grid[i][j] == "E" {
				end[0] = i
				end[1] = j
			}
		}
	}
	shortDis(grid, start, end, 5)
}
func shortDis(grid [][]string, pos, end [2]int, k int) {
	n := len(grid)
	m := len(grid[0])
	dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	e_k := make([][]int, n)
	for i := 0; i < n; i++ {
		e_k[i] = make([]int, m)
		for j := 0; j < m; j++ {
			e_k[i][j] = -1
		}
	}
	start := Node{
		x:    pos[0],
		y:    pos[1],
		step: 0,
		k:    k,
	}
	q := make([]Node, 0)
	q = append(q, start)
	for len(q) != 0 {
		cur_node := q[0]
		q = q[1:]
		if cur_node.x == end[0] && cur_node.y == end[1] {
			fmt.Println(cur_node.step)
			return
		}
		for i := 0; i < 5; i++ {
			next_node := Node{
				x:    0,
				y:    0,
				step: 0,
				k:    0,
			}
			if i < 4 {
				next_node = Node{
					x:    cur_node.x + dirs[i][0],
					y:    cur_node.y + dirs[i][1],
					step: cur_node.step,
					k:    cur_node.k,
				}

			} else {
				next_node = Node{
					x:    n - cur_node.x - 1,
					y:    m - cur_node.y - 1,
					step: cur_node.step,
					k:    cur_node.k - 1,
				}
			}
			if !check(grid, next_node, n, m) {
				continue
			}
			if next_node.k > e_k[next_node.x][next_node.y] {
				next_node.step++
				e_k[next_node.x][next_node.y] = next_node.k
				q = append(q, next_node)
			}
		}
	}
	fmt.Println(-1)
}

func check(grid [][]string, node Node, n, m int) bool {
	if !(0 <= node.x && node.x < n && 0 <= node.y && node.y < m) {
		return false
	}
	if node.k < 0 {
		return false
	}
	if grid[node.x][node.y] == "#" {
		return false
	}
	return true
}

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
struct node {
    int x;
    int y;
    int fly;
};

vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int bfs(int x, int y, vector<vector<char>>& map, int n, int m, pair<int, int> end) {
    queue<node> que;
    que.push({x, y, 0});

    int level = 0;

    while (!que.empty()) {
        int size = que.size();

        for (int i = 0; i < size; ++i) {
            node nd = que.front();
            que.pop();
            x = nd.x;
            y = nd.y;
            if (x == end.first && y == end.second) {
                return level;
            }

            for (int j = 0; j < 4; ++j) { //先尝试普通走，尽量不使用飞行器
                int nx = x + dir[j][0];
                int ny = y + dir[j][1];

                if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == '.') {
                    map[nx][ny] = '#';  //已经到访过
                    que.push({nx, ny, nd.fly});
                }
            }

            if (nd.fly < 5) {
                int nx = n - 1 - x;
                int ny = m - 1 - y;

                if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == '.') {
                    map[nx][ny] = '#';
                    que.push({nx, ny, nd.fly + 1});
                }

            }
        }
        ++level;
    }
    return -1;

}


int main() {
    int n, m;

    cin >> n >> m;
    pair<int, int> start;
    pair<int, int> end;

    vector<vector<char>> map(n, vector<char> (m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> map[i][j];
            if (map[i][j] == 'S') {
                start.first = i;
                start.second = j;
            }
            if (map[i][j] == 'E') {
                end.first = i;
                end.second = j;
                map[i][j] = '.'; 
            }
        }
    }

    cout << bfs(start.first, start.second, map, n, m, end);


    return 0;

}

'''
BFS加记录结点的当前代价以及剩余的转移次数的信息
'''
import queue

class Node():
    def __init__(self) -> None:
        self.x = None
        self.y = None
        self.c = None
        self.t = None

def check(node):
    if 0<=node.x<n and 0<=node.y<m and node.t>=0 and vis[node.x][node.y]==0 and Mat[node.x][node.y]!='#':
        return True
    return False

def BFS(node):
    Q = queue.Queue()
    Q.put(node)
    while Q.qsize():
        node = Q.get()
        if node.x == ex and node.y == ey:
            return node.c
        for i in range(5):
            temp = Node()
            if i<4:
                temp.x = node.x+dirs[i][0]
                temp.y = node.y+dirs[i][1]
                temp.c = node.c+1
                temp.t = node.t
            else:
                temp.x = n-1-node.x
                temp.y = m-1-node.y
                temp.c = node.c+1
                temp.t = node.t-1

            if check(temp):
                vis[temp.x][temp.y]=1
                Q.put(temp)
    return -1

while True:
    try:
        dirs = [[0,1],[1,0],[0,-1],[-1,0]]
        n,m = map(int,input().split())
        vis = [[0]*m for _ in range(n)]
        Mat = []
        for i in range(n):
            Mat.append(list(input()))
        
        sx,sy=-1,-1
        ex,ey=-1,-1
        for i in range(n):
            for j in range(m):
                if Mat[i][j] == 'S':
                    sx,sy=i,j
                if Mat[i][j] == 'E':
                    ex,ey=i,j
        
        sn = Node()
        sn.x,sn.y,sn.t,sn.c=sx,sy,5,0
        vis[sn.x][sn.y]=1
        print(BFS(sn))

    except:
        break

'''

4 4
#S..
E#..
#...
....

'''

// C++, 广度搜索

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int y = 0, x = 0;
    // 获取行与列的大小
    cin >> y >> x;
    
    vector<string> data(y);
    string s;
    int idx = 0;
    // 获取迷宫数据
    while(cin >> s)
    {
        data[idx] = std::move(s);
        idx++;
    }
    
    // 广度优先探索, 只将那些新探索到的或者步数变小的位置加入队列
    queue<pair<int,int>> q;
    
    // 用于和迷宫进行映射, 每一格保存最小步数以及剩余飞行器
    // 初始化将每格步数设为INT_MAX, 飞行器为5
    vector<vector<pair<int,int>>> step(y, vector<pair<int,int>>(x, {INT_MAX, 5}));
    
    // 将玩家当前位置加入队列
    // 并且找出目标位置
    int tx = 0, ty = 0;
    for(int i=0; i<y; i++)
    {
        for(int k=0; k<x; k++)
        {
            // 找到玩家
            if(data[i][k] == 'S')
            {
                step[i][k] = {0, 5};
                q.push({i,k});
            }
            // 找到目标
            if(data[i][k] == 'E')
            {
                ty = i;
                tx = k;
            }
        }
    }
    
    while(!q.empty())
    {
        // 这里没必要多这一个size和while的, 但是懒得改了...
        int size = q.size();
        while(size > 0)
        {
            // 获取当前的位置
            int py = q.front().first;
            int px = q.front().second;
            q.pop();
            // 1. 尝试向上探索: py > 0, 同时上面不是障碍物
            if(py > 0 && data[py-1][px] != '#')
            {
                // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列
                if(step[py][px].first < step[py-1][px].first - 1)
                {
                    step[py-1][px] = step[py][px];
                    step[py-1][px].first++; // 加上当前这一步
                    q.push({py-1, px});
                }
            }
            // 2. 尝试向下探索
            if(py < y - 1 && data[py+1][px] != '#')
            {
                // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列
                if(step[py][px].first < step[py+1][px].first - 1)
                {
                    step[py+1][px] = step[py][px];
                    step[py+1][px].first++; // 加上当前这一步
                    q.push({py+1, px});
                }
            }
            // 3. 向左探索
            if(px > 0 && data[py][px - 1] != '#')
            {
                // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列
                if(step[py][px].first < step[py][px-1].first - 1)
                {
                    step[py][px-1] = step[py][px];
                    step[py][px-1].first++; // 加上当前这一步
                    q.push({py, px-1});
                }
            }
            // 4. 向右
            if(px < x - 1 && data[py][px + 1] != '#')
            {
                // 前进一步后, 该位置为未探索或步数更小时, 才进行更新并添加入队列
                if(step[py][px].first < step[py][px+1].first - 1)
                {
                    step[py][px+1] = step[py][px];
                    step[py][px+1].first++; // 加上当前这一步
                    q.push({py, px+1});
                }
            }            
            // 5. 飞行, 到达位置:(y-py+1), (x-px+1), 需要条件:1.还有飞行次数, 2. 飞跃目的地不是障碍物
            int fy = y-py-1;
            int fx = x-px-1;
            if(step[py][px].second > 0 && data[fy][fx] != '#')
            {
                // 飞跃后的位置是新位置, 或者步数更小才更新
                if(step[py][px].first < step[fy][fx].first - 1)
                {
                    step[fy][fx] = step[py][px];
                    step[fy][fx].first++;
                    step[fy][fx].second--;
                    q.push({fy,fx});
                }
            }
            size--;
        }
    }
    
    if(step[ty][tx].first == INT_MAX)
        cout << -1;
    else
        cout << step[ty][tx].first;
    
    return 0;
}