Submission #162100

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
 
import java.util.*;
import java.util.Map.Entry;
 
public class Main {
 
	public static boolean is_ok(int x, int y, int C, int R){
		if(x < 0 || y < 0 || x >= C || y >= R){
			return false;
		}else{
			return true;
		}
	}
	
	public static int[][] move_dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		final int R = sc.nextInt();
		final int C = sc.nextInt();
		final int sy = sc.nextInt() - 1;
		final int sx = sc.nextInt() - 1;
		final int gy = sc.nextInt() - 1;
		final int gx = sc.nextInt() - 1;
		
		boolean[][] wall = new boolean[R][C];
		
		for(int i = 0; i < R; i++){
			char[] in = sc.next().toCharArray();
			
			for(int j = 0; j < C; j++){
				wall[i][j] = in[j] == '#';
			}
		}
		
		LinkedList<Integer> x_queue = new LinkedList<Integer>();
		LinkedList<Integer> y_queue = new LinkedList<Integer>();
		LinkedList<Integer> time_queue = new LinkedList<Integer>();
		boolean[][] visited = new boolean[R][C];
		
		visited[sy][sx] = true;
		x_queue.add(sx);
		y_queue.add(sy);
		time_queue.add(0);
		
		while(!time_queue.isEmpty()){
			final int x = x_queue.poll();
			final int y = y_queue.poll();
			final int time = time_queue.poll();
			
			if(x == gx && y == gy){
				System.out.println(time);
				break;
			}
			
			
			for(int[] move : move_dir){
				final int nx = x + move[0];
				final int ny = y + move[1];
				
				if(!is_ok(nx, ny, C, R)){
					continue;
				}else if(visited[ny][nx]){
					continue;
				}else if(wall[ny][nx]){
					continue;
				}
				
				visited[ny][nx] = true;
				x_queue.add(nx);
				y_queue.add(ny);
				time_queue.add(time + 1);
			}
		}
		
		
	}
	
	public static class Scanner {
		
		private BufferedReader br;
		private StringTokenizer tok;
		
		public Scanner(InputStream is) throws IOException{
			br = new BufferedReader(new InputStreamReader(is));
			getLine();
		}
		
		private void getLine() throws IOException{
			while(tok == null || !tok.hasMoreTokens()){
				tok = new StringTokenizer(br.readLine());
			}
		}
		
		private boolean hasNext(){
			return tok.hasMoreTokens();
		}
		
		public String next() throws IOException{
			if(hasNext()){
				return tok.nextToken();
			}else{
				getLine();
				return tok.nextToken();
			}
		}
		
		public int nextInt() throws IOException{
			if(hasNext()){
				return Integer.parseInt(tok.nextToken());
			}else{
				getLine();
				return Integer.parseInt(tok.nextToken());
			}
		}
		
		public long nextLong() throws IOException{
			if(hasNext()){
				return Long.parseLong(tok.nextToken());
			}else{
				getLine();
				return Long.parseLong(tok.nextToken());
			}
		}
		
		public double nextDouble() throws IOException{
			if(hasNext()){
				return Double.parseDouble(tok.nextToken());
			}else{
				getLine();
				return Double.parseDouble(tok.nextToken());
			}
		}
	}
}

Submission Info

Judge Result