Submission #1511608
Source Code Expand
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int R = sc.nextInt(); int C = sc.nextInt(); int sy = sc.nextInt(); int sx= sc.nextInt(); int gy = sc.nextInt(); int gx= sc.nextInt(); String tmp=""; String c_ij[][]=new String[R][C]; for(int i=0;i<R;i++) { tmp=sc.next(); for(int j=0;j<C;j++) { c_ij[i][j]=""+tmp.charAt(j); } } System.out.println(new BreadthFirstSearch(sy,sx,gy,gx,c_ij).shortestPath()); } } class BreadthFirstSearch { int sy = 0; int sx = 0; int gy = 0; int gx = 0; String c_ij[][]; BreadthFirstSearch(int sy,int sx,int gy,int gx,String c_ij[][]) { this.sy=sy-1; this.sx=sx-1; this.gy=gy-1; this.gx=gx-1; this.c_ij=c_ij; // System.out.print(this.gx+"|"+this.gy+"|"+gx+"|"+gy); } String shortestPath() { ArrayQueue<XY> que = new ArrayQueue<XY>(); que.enqueue(new XY(sx,sy)); c_ij[sx][sy]=0+""; XY xy; for(;;) { if(que.size()==0) { break; } xy=que.dequeue(); // System.out.println(xy.x+"|"+xy.y); if(c_ij[xy.x][xy.y-1].equals(".")) { que.enqueue(new XY(xy.x,xy.y-1)); c_ij[xy.x][xy.y-1]=(Integer.parseInt(c_ij[xy.x][xy.y])+1)+""; } if(c_ij[xy.x][xy.y+1].equals(".")) { que.enqueue(new XY(xy.x,xy.y+1)); c_ij[xy.x][xy.y+1]=(Integer.parseInt(c_ij[xy.x][xy.y])+1)+""; } if(c_ij[xy.x-1][xy.y].equals(".")) { que.enqueue(new XY(xy.x-1,xy.y)); c_ij[xy.x-1][xy.y]=(Integer.parseInt(c_ij[xy.x][xy.y])+1)+""; } if(c_ij[xy.x+1][xy.y].equals(".")) { que.enqueue(new XY(xy.x+1,xy.y)); c_ij[xy.x+1][xy.y]=(Integer.parseInt(c_ij[xy.x][xy.y])+1)+""; } // for(int i=0;i<7;i++) // { // for(int j=0;j<8;j++) // { // System.out.print(c_ij[i][j]); // } // System.out.println(""); // } } // System.out.print(gx+"|"+gy); return c_ij[gy][gx]; } class XY { int x=0; int y=0; XY(int x,int y) { this.x=x; this.y=y; } } class ArrayQueue<T> extends ArrayList<T> { public ArrayQueue(){ super(); } public void enqueue(T data){ super.add(data); } public T dequeue() { T val= super.get(0); super.remove(0); return val; } } }
Submission Info
Submission Time | |
---|---|
Task | C - 幅優先探索 |
User | junya0124 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 2618 Byte |
Status | AC |
Exec Time | 122 ms |
Memory | 24020 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
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 | 93 ms | 18772 KB |
subtask0_sample02.txt | AC | 93 ms | 20052 KB |
subtask0_sample03.txt | AC | 108 ms | 22100 KB |
subtask1_01.txt | AC | 108 ms | 24020 KB |
subtask1_02.txt | AC | 109 ms | 20692 KB |
subtask1_03.txt | AC | 109 ms | 18772 KB |
subtask1_04.txt | AC | 121 ms | 23892 KB |
subtask1_05.txt | AC | 113 ms | 20820 KB |
subtask1_06.txt | AC | 111 ms | 19284 KB |
subtask1_07.txt | AC | 95 ms | 17364 KB |
subtask1_08.txt | AC | 98 ms | 21716 KB |
subtask1_09.txt | AC | 109 ms | 21844 KB |
subtask1_10.txt | AC | 111 ms | 21844 KB |
subtask1_11.txt | AC | 119 ms | 20052 KB |
subtask1_12.txt | AC | 122 ms | 21972 KB |
subtask1_13.txt | AC | 109 ms | 21844 KB |
subtask1_14.txt | AC | 98 ms | 19924 KB |
subtask1_15.txt | AC | 109 ms | 22100 KB |
subtask1_16.txt | AC | 119 ms | 22228 KB |
subtask1_17.txt | AC | 108 ms | 18900 KB |
subtask1_18.txt | AC | 109 ms | 20180 KB |
subtask1_19.txt | AC | 116 ms | 20052 KB |
subtask1_20.txt | AC | 107 ms | 20180 KB |
subtask1_21.txt | AC | 117 ms | 20052 KB |
subtask1_22.txt | AC | 116 ms | 20052 KB |