Submission #1511514


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 rls1021
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 2618 Byte
Status AC
Exec Time 130 ms
Memory 24020 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 97 ms 20564 KB
subtask0_sample02.txt AC 99 ms 23764 KB
subtask0_sample03.txt AC 110 ms 20052 KB
subtask1_01.txt AC 130 ms 19796 KB
subtask1_02.txt AC 106 ms 21076 KB
subtask1_03.txt AC 115 ms 20688 KB
subtask1_04.txt AC 124 ms 19924 KB
subtask1_05.txt AC 123 ms 20052 KB
subtask1_06.txt AC 109 ms 20944 KB
subtask1_07.txt AC 100 ms 21716 KB
subtask1_08.txt AC 99 ms 18644 KB
subtask1_09.txt AC 108 ms 18772 KB
subtask1_10.txt AC 110 ms 21716 KB
subtask1_11.txt AC 117 ms 22100 KB
subtask1_12.txt AC 110 ms 19540 KB
subtask1_13.txt AC 113 ms 17364 KB
subtask1_14.txt AC 99 ms 21204 KB
subtask1_15.txt AC 119 ms 20052 KB
subtask1_16.txt AC 124 ms 21332 KB
subtask1_17.txt AC 117 ms 22868 KB
subtask1_18.txt AC 109 ms 20052 KB
subtask1_19.txt AC 109 ms 20308 KB
subtask1_20.txt AC 109 ms 20052 KB
subtask1_21.txt AC 117 ms 21972 KB
subtask1_22.txt AC 108 ms 24020 KB