[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;
    }
}