ac (BFS求解)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] arr = new char[n][m];
        for(int i=0;i<n;i++){
            String tmp = sc.next();
            arr[i] =  tmp.toCharArray();
        }

        int ans = bfs(arr, n, m, 0, 0, n-1, m-1);
        System.out.println(ans);
    }

    static boolean positionOk(int n, int m, int i, int j){
        if(i < 0 || i >= n || j < 0 || j >= m){
            return false;
        }
        return true;
    }
    static int[][] dir = {
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };

    static int bfs(char[][] arr, int n, int m, int ci, int cj, int ei, int ej){
        if(arr[ci][cj] == 0){
            return -1;
        }
        Queue<Integer> heightQueue = new LinkedList<>();
        Queue<Integer> posQueue = new LinkedList<>();
        heightQueue.offer(1);
        posQueue.offer( ci * m + cj);
        boolean[] vis = new boolean[n*m];
        vis[ci * m + cj] = true;
        while (!posQueue.isEmpty()){
            int curHeight = heightQueue.poll();
            int curPos = posQueue.poll();
            int curi = curPos / m;
            int curj = curPos % m;
            if(curi == ei && curj == ej){
                return curHeight;
            }
            for(int i=0;i<4;i++){
                int ni = curi + dir[i][0];
                int nj = curj + dir[i][1];
                int index = ni * m + nj;
                if(positionOk(n, m, ni, nj) && arr[ni][nj] == '1' && !vis[index]){
                    posQueue.offer(index);
                    heightQueue.offer(curHeight + 1);
                    vis[index] = true;
                }
            }
        }
        return -1;
    }


}
/*
4 5
11011
11111
11111
00001
8
*/

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] arr = new char[n][m];
        for(int i=0;i<n;i++){
            String tmp = sc.next();
            arr[i] =  tmp.toCharArray();
        }
        if(arr[0][0] != 0){
            boolean[][] vis = new boolean[n][m];
            vis[0][0] = true;
            dfs(arr, n, m, 0, 0, n-1, m-1, 1, vis);
            if(minStep < Integer.MAX_VALUE){
                System.out.println(minStep);
            }else {
                System.out.println(-1);
            }
        }else {
            System.out.println(-1);
        }
    }

    static boolean positionOk(int n, int m, int i, int j){
        if(i < 0 || i >= n || j < 0 || j >= m){
            return false;
        }
        return true;
    }
    static int[][] dir = {
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };
    static int minStep = Integer.MAX_VALUE;

    static void dfs(char[][] arr, int n, int m, int ci, int cj, int ei, int ej, int step, boolean[][] vis ){
        if(step >= minStep){
            return;
        }
        if(ci == ei && cj == ej){
            if(step < minStep){
                minStep = step;
            }
//            System.out.println(ci + " " + cj + " " + step);
        }
        for(int i=0;i<4;i++){
            int ni = ci + dir[i][0];
            int nj = cj + dir[i][1];
            if(positionOk(n, m, ni, nj) && !vis[ni][nj] && arr[ni][nj] == '1'){
                vis[ni][nj] = true;
                dfs(arr, n, m, ni, nj, ei, ej, step + 1, vis);
                vis[ni][nj] = false;
            }
        }
    }

}
/*
4 5
11011
11111
11111
00001
8
*/