Submission #1435974


Source Code Expand

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * http://abc007.contest.atcoder.jp/tasks/abc007_3
 */
public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int R = sc.nextInt();
		int C = sc.nextInt();
		int s[] = new int[2];
		int g[] = new int[2];
		int cost[][]  = new int[R][C];
		char field[][]  = new char[R][C];
		s[0] = sc.nextInt()-1;
		s[1] = sc.nextInt()-1;
		g[0] = sc.nextInt()-1;
		g[1] = sc.nextInt()-1;
		for(int y=0; y<R; y++){
			String c = sc.next();
			for(int x=0; x<C; x++){
				cost[y][x] = -1;
				field[y][x] = (char) c.charAt(x);
			}
		}
		sc.close();
		
		List<Pos> search = new ArrayList<Pos>();
		search.add(new Pos(s[0],s[1]));
		cost[s[0]][s[1]]=0;
		
		while(true){
			
			if(search.size()==0){
				break;
			}
			
			Pos current = search.remove(0);
			int x = current.x;
			int y = current.y;
			
			Pos[] candidates = { new Pos(y,x-1), new Pos(y, x+1), new Pos(y-1,x), new Pos(y+1,x)};
			
			int minCost = Integer.MAX_VALUE;
			for(Pos pos: candidates){
				if(field[pos.y][pos.x] == '.'){
					if(cost[pos.y][pos.x] == -1){
						cost[pos.y][pos.x] = cost[y][x]+1;
						search.add(new Pos(pos.y,pos.x));
					}else{
						minCost = Math.min(minCost, cost[pos.y][pos.x]);
					}
				}
			}

		}
		
		System.out.println(cost[g[0]][g[1]]);
		
	}
	
	private static class Pos{
		Pos(final int y, final int x){
			this.x = x;
			this.y = y;
		}
		int x;
		int y;
	}

}

Submission Info

Submission Time
Task C - 幅優先探索
User namayaki
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 1562 Byte
Status AC
Exec Time 108 ms
Memory 23636 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 91 ms 21844 KB
subtask0_sample02.txt AC 94 ms 23636 KB
subtask0_sample03.txt AC 100 ms 18644 KB
subtask1_01.txt AC 100 ms 21204 KB
subtask1_02.txt AC 98 ms 19924 KB
subtask1_03.txt AC 99 ms 19924 KB
subtask1_04.txt AC 101 ms 19796 KB
subtask1_05.txt AC 102 ms 19796 KB
subtask1_06.txt AC 101 ms 20820 KB
subtask1_07.txt AC 91 ms 19924 KB
subtask1_08.txt AC 97 ms 17748 KB
subtask1_09.txt AC 104 ms 19024 KB
subtask1_10.txt AC 108 ms 18644 KB
subtask1_11.txt AC 101 ms 19156 KB
subtask1_12.txt AC 100 ms 20556 KB
subtask1_13.txt AC 107 ms 21456 KB
subtask1_14.txt AC 97 ms 21972 KB
subtask1_15.txt AC 100 ms 17876 KB
subtask1_16.txt AC 100 ms 21716 KB
subtask1_17.txt AC 106 ms 18900 KB
subtask1_18.txt AC 99 ms 19924 KB
subtask1_19.txt AC 99 ms 18772 KB
subtask1_20.txt AC 100 ms 16972 KB
subtask1_21.txt AC 100 ms 19284 KB
subtask1_22.txt AC 101 ms 21204 KB