[2020ココアブラインド]移動ブロック
37312 ワード
リンク
「プログラマ」ブロックの移動
質問する
ロボット開発者の「無知」は、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)位置に移動するのに要する最小時間を返すために、ソルバを完了します.
せいげんじょうけん
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秒かかる.
プロセス
コード#コード#
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;
}
}
Reference
この問題について([2020ココアブラインド]移動ブロック), 我々は、より多くの情報をここで見つけました https://velog.io/@wnsdud2336/2020-카카오-블라인드-블록-이동하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol