[2020ココアブラインド]移動ブロック


リンク


「プログラマ」ブロックの移動

質問する


ロボット開発者の「無知」は、1カ月後に迫った「ココアカップロボットコンテスト」で出品されるロボットを準備している.準備中のロボットは2 x 1サイズのロボットで、「無知」は「0」と「1」からなるN x Nサイズの地図で、2 x 1サイズのロボット(N,N)の位置にプログラミングされて移動します.オートマトンが移動する地図は左上隅の座標(1,1)で表され、地図内の数字「0」はスペース、「1」は壁を表す.ロボットは壁のあるセルや地図の外に移動できません.ロボットは座標(1、1)の位置から始め、水平方向に移動し、下図のように前後を区別しません.

オートマチックが移動すると、現在の配置状態が維持されます.たとえば、上の図で1つのセル(1,2)、(1,3)を右に移動すると、2つのセル(2,1)、(2,2)が占有されます.ロボットが占有する2つの格子のいずれも(N,N)位置に到達できる.
オートマチックは以下の条件で回転できます.

上の図に示すように、オートマチックは90度回転できます.ただし、ロボットが占有する2つのセルのうち、いずれも軸であってもよいが、回転方向(軸のセルに対して対角線方向)には壁がない必要がある.ロボットが1マスを移動したり90度回転したりするのに要する時間は正確に1秒です.
「0」と「1」からなる地図指示板が与えられた場合、ロボットが(N,N)位置に移動するのに要する最小時間を返すために、ソルバを完了します.

せいげんじょうけん

  • boardの辺長は5以上100以下である.
  • boardの要素は0または1である.
  • ロボットが最初に配置したセル(1、1)、(1、2)は常にゼロです.
  • ロボットが常に目的地に到達している場合のみ入力します.
  • I/O例


    board result
    [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7

    I/O例説明


    問題の例を示します.
    ロボットは1つのセルを右に移動し、(1,3)セルを軸の反時計回りに90度回転させます.再度、3コマ下に移動すると、ロボットは(4,3)、(5,3)の2コマを占有します.(5,3)軸に沿って時計回りに90度回転し、右に1マス移動すると(N,N)に着きます.したがって、目的地に到着するには少なくとも7秒かかる.

    プロセス

  • 最初はBFS問題と思っていたが、すぐに解決できた.でも回転するので少し複雑になります.
  • [YJYOON's様]ブログでは、ロボットが方向Dに平行移動可能であれば、方向Dを2種類回転可能です.参考に、回転可能か確認しました.
  • Robotランクを発表し、移動可能座標を抽出する方法を確立し、近づきやすい.
  • 各座標の横方向と縦方向に動的計画法を採用し、効率を向上させた.
  • コード#コード#

    import java.util.*;
    
    class Solution {
        
        class Robot {
            public Robot(int time, int x1, int y1, int x2, int y2) {
                this.time = time;
                this.x1 = x1;
                this.y1 = y1;
                this.x2 = x2;
                this.y2 = y2;
            }
            public int time;
            public int x1;
            public int y1;
            public int x2;
            public int y2;
            
            public ArrayList<int[]> getPosListRotate(int[][] board) {
                ArrayList<int[]> result = new ArrayList<int[]>();
                //수평일때
                if(y1 == y2){
                    //아래로 회전
                    if(canMove(x1,y1+1,x2,y2+1,board)){
                        result.add(new int[]{x1,y1, x1, y1+1});
                        result.add(new int[]{x2,y2, x2, y2+1});
                    }
                    //위로 회전
                    if(canMove(x1,y1-1,x2,y2-1,board)){
                        result.add(new int[]{x1,y1-1, x1, y1});
                        result.add(new int[]{x2,y2-1, x2, y2});
                    }
                }
                //수직일때
                if(x1 == x2){
                    
                    //왼쪽으로 회전
                    if(canMove(x1-1,y1,x2-1,y2,board)){
                        result.add(new int[]{x1-1,y1, x1, y1});
                        result.add(new int[]{x2-1,y2, x2, y2});
                    }
                    //오른쪽으로 회전
                    if(canMove(x1+1,y1,x2+1,y2,board)){
                        result.add(new int[]{x1,y1, x1+1, y1});
                        result.add(new int[]{x2,y2, x2+1, y2});
                    }
                }
                return result;
            }
            public ArrayList<int[]> getPosListMove(int[][] board) {
                ArrayList<int[]> result = new ArrayList<int[]>();
                if(canMove(x1+1,y1,x2+1,y2,board)) result.add(new int[] {x1+1,y1,x2+1,y2});
                if(canMove(x1-1,y1,x2-1,y2,board)) result.add(new int[] {x1-1,y1,x2-1,y2});
                if(canMove(x1,y1+1,x2,y2+1,board)) result.add(new int[] {x1,y1+1,x2,y2+1});
                if(canMove(x1,y1-1,x2,y2-1,board)) result.add(new int[] {x1,y1-1,x2,y2-1});
                
                return result;
            }
            public boolean canMove(int x1, int y1,int x2, int y2, int[][] board){
                if(x1 < 0 || x2 >= board.length || y1 < 0 || y2 >= board.length) return false;
                if(board[y1][x1] == 1 || board[y2][x2] == 1) return false;
                return true;
            }
        }
        int[][][] memo;
        public int solution(int[][] board) {
            memo = new int[board.length][board.length][2];
            for(int i=0; i<board.length; i++)
                for(int j=0; j<board.length; j++){
                    memo[i][j][0] = 10001; //가로
                    memo[i][j][1] = 10001; //세로
                }
            
            Queue<Robot> queue = new LinkedList<Robot>();
            queue.offer(new Robot(0,0,0,1,0));
            
            while(!queue.isEmpty()){ 
                Robot robot = queue.poll();
                
                //도착
                if(robot.x2 == board.length-1 && robot.y2 == board.length-1) 
                    // break;
                    return robot.time;
                
                //메모이제이션
                if(robot.x1 == robot.x2 ) {//세로
                    if(robot.time >= memo[robot.y1][robot.x1][1]) 
                        continue;
                    else 
                        memo[robot.y1][robot.x1][1] = robot.time;
                }
                
                if(robot.y1 == robot.y2){ //가로
                   if(robot.time >= memo[robot.y1][robot.x1][0]) 
                        continue;
                    else 
                        memo[robot.y1][robot.x1][0] = robot.time;
                } 
                
                //탐색
                for(int[] pos : robot.getPosListMove(board))
                    queue.add(new Robot(robot.time+1,pos[0],pos[1],pos[2],pos[3]));
                for(int[] pos : robot.getPosListRotate(board))
                    queue.add(new Robot(robot.time+1,pos[0],pos[1],pos[2],pos[3]));
            }
            
            return 0;
        }
    }