华为 第二题 跳马 80%

// 感觉是没有考虑到边界情况，不是超时，是答案错误。不过感觉可以dp优化下，dfs纯暴搜确实捞

import java.util.Scanner;

public class Main {
    static int m, n;
    static long[][][] PATH;
    static char[][] board;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        sc.nextLine();
        board = new char[m][n];
        for (int i = 0; i < m; i++) {
            String s = sc.nextLine();
            board[i] = s.toCharArray();
        }
        PATH = new long[m][n][2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                PATH[i][j][0] = Integer.MAX_VALUE;
                PATH[i][j][1] = Integer.MAX_VALUE;
            }
        }
        dfs(0, 0, 0, 0);
        System.out.println(Math.min(PATH[m-1][n-1][0],PATH[m-1][n-1][1]) >= Integer.MAX_VALUE ? -1 : Math.min(PATH[m-1][n-1][0],PATH[m-1][n-1][1]));
    }
    public static void dfs(int state, int i, int j, int path){
        if (i >= 0 && j >= 0 && i < m && j < n && path < PATH[i][j][state] && board[i][j] != 'X') {
            PATH[i][j][state] = path;
            if (state == 0) {
                dfs(state, i + 1, j, path + 1);
                dfs(state, i , j+ 1, path + 1);
            }
            if (state == 1) {
                dfs(state, i-2, j+1, path+1);
                dfs(state, i+1, j+2, path+1);
                dfs(state, i+1, j-2, path+1);
                dfs(state, i+2, j+1, path+1);
                dfs(state, i+2, j-1, path+1);
            }

            if (board[i][j] == 'S'){
                state = toggle(state);
                path++;
                if (state == 0) {
                    dfs(state, i + 1, j, path + 1);
                    dfs(state, i , j+ 1, path + 1);
                }
                if (state == 1) {
                    dfs(state, i-2, j+1, path+1);
                    dfs(state, i+1, j+2, path+1);
                    dfs(state, i+2, j+1, path+1);
                }
            }
        }
    }
    static int toggle(int x) {
        return x == 0 ? 1 : 0;
    }
}