아직 계정이 없으신가요? 회원가입

Dev. Talk

GINI야 도와줘 반례 부탁드립니다

회원사진dongwoni3
91 views2021-10-17 13:44


import java.util.*;
import java.io.*;

class Point{
    int x,y;
    public Point(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class Main
{
    
    static int R, C, startX,startY,destY,destX;
    static char[][] map;
    static int time=0;
    public static void main(String args[])
    {
        inputProcessing();
        Queue<Point> q= new LinkedList<>();
        Point p=new Point(startX,startY);
        boolean[][] visited=new boolean[R][C];
        visited[startX][startY]=true;
        q.offer(p);
        traverse(q,visited);
        if (0==time) System.out.println("FAIL");
        else System.out.println(time);
        
            
    }

    public static void traverse(Queue<Point> q, boolean[][] visited){
        Queue<Point> tmpQ=new LinkedList<Point>();
        while(!q.isEmpty()){
            Point p=q.poll();
            //up
            int x=p.x, y=p.y;
            //System.out.print(" time="+time);
            if(x==destX&&y==destY) {
                return;
            }
            if(isValid(x-1,y,visited)) {
                tmpQ.offer(new Point(x-1,y));
                visited[x-1][y]=true;
            }
            //down
            if(isValid(x+1,y,visited)){
                tmpQ.offer(new Point(x+1,y));
                visited[x+1][y]=true;
            }
            //right
            if(isValid(x,y+1,visited)){
                tmpQ.offer(new Point(x,y+1));
                visited[x][y+1]=true;
            } 
            //left
            if(isValid(x,y-1,visited)){
                tmpQ.offer(new Point(x,y-1));
                visited[x][y-1]=true;
            }
        }
        //System.out.println("Queue="+tmpQ.size());
        if(tmpQ.isEmpty()) {
            time=0;
            return;
        }
        time++;
        traverse(tmpQ, visited);
    }

    static boolean isValid(int x,int y, boolean[][] visited){
        if(0>x||R<=x||0>y||C<=y) return false;
        if('*'==map[x][y]||'X'==map[x][y]) return false;
        if(visited[x][y]) return false;
        return true;
    }
    public static void inputProcessing(){
        Scanner sc=new Scanner(System.in);
        R=sc.nextInt();
        C=sc.nextInt();
        String str;
        map=new char[R][C];
        for(int i=0;i<R;i++){
            str=sc.next();
            for(int j=0;j<C;j++){
                map[i][j]=str.charAt(j);
                if('H'==map[i][j]) {
                    startX=i;
                    startY=j;
                }
                else if('W'==map[i][j]) {
                    destX=i;
                    destY=j;
                }
            }
        }
    }


}