Submission #162591

---

Source Code Expand

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	private static int R, C;
	private static Pos s;
	private static Pos g;
	private static char[][] p;
	private static int[][] dist;
	private static int[] dx = {1,0,-1,0}, dy = {0,1,0,-1};
	
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String[] arrays = line.split(" ");
		
		R = Integer.parseInt(arrays[0]);
		C = Integer.parseInt(arrays[1]);
		
		line = br.readLine();
		arrays = line.split(" ");
		
		s = new Pos(Integer.parseInt(arrays[0])-1, Integer.parseInt(arrays[1])-1);
		
		line = br.readLine();
		arrays = line.split(" ");
		g = new Pos(Integer.parseInt(arrays[0])-1, Integer.parseInt(arrays[1])-1);
		
		p = new char[R][C];
		dist = new int[R][C];
		for(int i=0;i<R;i++){
			line = br.readLine();
			p[i] = line.toCharArray();
		}
		search();
		System.out.println(dist[g.Y][g.X]);
	}
	
	private static void search(){
		Queue<Pos> que = new LinkedList<Pos>();
		
		int[] cur_p = new int[2];
		
		que.offer(s);
		dist[s.Y][s.X] = 0;

		while(que.size() > 0) {
			Pos point = que.poll();
			if(point.Y == g.Y && point.X == g.X) break; 
			for(int i = 0; i < 4; i++) {
				cur_p[0] = point.Y + dy[i];
				cur_p[1] = point.X + dx[i];
				
				if(pos_check(cur_p)) {
					que.offer(new Pos(cur_p[0], cur_p[1]));
					dist[cur_p[0]][cur_p[1]] = dist[point.Y][point.X] + 1; 
				}
				
			}
		}
	}
	private static boolean pos_check(int[] pos){

		if(0 > pos[0] || 0 > pos[1] || R <= pos[0] || C <= pos[1]){
			return false;
		}
		if(p[pos[0]][pos[1]] == '#'){
			return false;
		}
		if((dist[pos[0]][pos[1]] != 0)){
			return false;
		}
		return true;
	}
	private static class Pos {
		private int Y, X;
		
		public Pos(int Y, int X) {
			this.Y = Y;
			this.X = X;
		} 
	}
}

Submission Info

Judge Result