BOJ2178미로탐색(최소이동구하기)

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

import java.io.*;
import java.util.*;
public class Main
{   
    static int n;
	static int m;
	static int[][] map;
	static int[] move_r = new int[]{1,0,-1,0};
	static int[] move_c = new int[]{0,1,0,-1};
	
	public static class Node{
	    public int r;
	    public int c;
	    public int step;
	    public Node(int r, int c, int step){
	        this.r=r;
	        this.c=c;
	        this.step=step;
	    }
	}
	
	
	public static int bfs(Node start){
	    Queue<Node> q = new LinkedList();
	    boolean[][] visited = new boolean[n][m];
	    q.offer(start);
	    
	    while(q.size()>0){
	        Node node = q.poll();
	        
	        if(node.r==n-1 && node.c==m-1){
	            return node.step;
	        }
	        if(visited[node.r][node.c]||map[node.r][node.c]==0){
	            continue;
	        }
	        visited[node.r][node.c]= true;
	        for(int i=0; i<4;i++){
	            if(node.r+move_r[i]>=0 && node.r+move_r[i]<n && node.c+move_c[i]>=0 && node.c+move_c[i]<m){
	                if(!visited[node.r+move_r[i]][node.c+move_c[i]] && map[node.r+move_r[i]][node.c+move_c[i]]!=0){
	                    q.offer(new Node(node.r+move_r[i],node.c+move_c[i],node.step+1));
	                }
	            }
	        }
	    }
	    return 0;
	}
		
    
    
    
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input1 = br.readLine().split(" ");
		n = Integer.parseInt(input1[0]);
		m = Integer.parseInt(input1[1]);
		
		
		map = new int[n][m];
		for(int i=0; i<n;i++){
		    String[] input2= br.readLine().split("");
		    for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(input2[j]);
		    }
		}
		
		int ans = bfs(new Node(0,0,1));
		System.out.println(ans);
		
		
		
	}
}

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

class Main {
    static int n, m;
    static int[][] maze;
    static int[][] visited;

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        maze = new int[n + 1][m + 1];
        visited = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i ++) {
            String line = sc.next();
            for(int j = 1 ; j <= m ; j++) {
                maze[i][j] = line.charAt(j - 1) - '0';
            }
        }
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(1, 1));
        visited[1][1] = 1;
        while(!q.isEmpty()) {
            Point now = q.poll();
            for(int i = 0; i < 4; i++) {
                int nr = now.r + dr[i];
                int nc = now.c + dc[i];
                if(nc <= 0 || nc > m || nr <= 0 || nr > n) continue;
                if(visited[nr][nc] == 0 && maze[nr][nc] == 1) {
                    visited[nr][nc] = visited[now.r][now.c] + 1;
                    q.add(new Point(nr, nc));
                }
            }
        }
        System.out.println(visited[n][m]);
    }
}

class Point {
    int r, c;
    Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}