Programmersに公開された2023 KAKAO BLIND RECRUITMENT（2023年新入債務第一次オンラインコーディングテスト）の中でLv.3に設定されている迷路脱出命令語です。
1. 問題と条件
問題
n x m格子迷路が与えられます。貴方は迷路の（x、y）から終発し（r、c）に移動して脱出しないといけないです。
但し、迷路を脱出する条件が三つあります。
格子の外には出られません。
（x、y）から（r、c）まで移動する距離が合計kでなければいけないです。この時、（x、y）と（r、c）格子を含めて、同じ格子を2回以上訪問しても良いです。
迷路から脱出した経路を文字列で表した時、文字列が辞書順で一番早い経路で脱出しないといけないです。
移動経路を下記のように文字列に変えれます。
l: 左に一行移動
r: 右に一行移動
u: 上に一行移動
d: 下に一行移動
例えは、左に一行、上に一行、左に一行動いたら、文字列「lul」で表せます。
迷路では隣接している上、下、左、右格子に一行ずつ移動できます。
入力
格子の大きさを意味する定数n、m、出発位置を意味する定数x、y、脱出地点を意味する定数r、c、脱出まで移動しないといけない距離を意味する定数kがパラメーターで与えられます。
2 ≤ n (= 迷路の縦の長さ) ≤ 50
2 ≤ m (= 迷路の横の長さ) ≤ 50
1 ≤ x ≤ n
1 ≤ y ≤ m
1 ≤ r ≤ n
1 ≤ c ≤ m
(x, y) ≠ (r, c)
1 ≤ k ≤ 2,500
出力
迷路を脱出するための経路をreturnするようsolution関数を完成して下さい。但し、上の条件通りに迷路を脱出できない場合「impossible」をreturnしないといけないです。
入出力の例
n | m | x | y | r | c | k | result |
3 | 4 | 2 | 3 | 3 | 1 | 5 | "dllrl" |
2 | 2 | 1 | 1 | 2 | 2 | 2 | "dr" |
3 | 3 | 1 | 2 | 3 | 3 | 4 | "impossible" |
2. 説明
動ける回数が決められていて、一回動く時上下左右1回ずつ動けます。同じ格子を何回訪問しても構わないっていう条件があるため、過ぎてきた経路座標を別に保存する必要はないです。全てのケースを全部計算する場合、kが最大2,500になっていて4の2,500勝という大まかな数字が出てくるので、全てのケースを検索するのは無理です。そのため、問題の３番条件である辞書順で一番早い経路が重要です。
辞書順で一番早い経路は一回の移動で辞書順で早い文字順で選択して移動したら完成できるため、辞書順で早い文字を適切に選択して指定された回数で（x、y）座標から（r、c）まで到達できたら、その後の検索は必要ないです。したがって、（x、y）座標で出発して（r、c）座標に移動するため、（x、y）座標を辞書順で早い順番で（d＞l＞r＞u）一行ずつ移動しながらkを1回ずつ消尽して、k＝０になる時（x、y）＝（r、c）になったら検索を終了するようアルゴリズムを作成したら解決できると思います。ここで検索時間を縮めるためをは下記の制限事項を追加する必要があります。
格子の外には出られないっていう規則があるので、次の移動が格子の外に行く場合は考慮しません。
動ける回数が指定されているため、回数が０になる時到着地点に到着出来るか検査して、到着出来ない移動をする場合を考慮しません。
1番条件の場合、[1 ≤ x ≤ n, 1 ≤ y ≤ m] 条件があるため、簡単に作成できると思います。
2番条件の場合、指定された回数で出発地点から最後の地点まで到達するのは下記のような規則があります。
上の絵みたいに（x、y）から（r、c）までの距離（最小移動回数）は |(x - r)| + |(y - c)| = 距離（最小移動回数）の式が完成されます。距離を出すことで、kの値が二つの条件を満足することで最後の地点に行けます。
k > 距離を満足するのとで最後の地点に辿り着けます。
一回に一行ずつ移動するため、kー距離＝追加移動距離（追加移動回数）になります。追加移動距離の場合、最後の地点まで戻って来る為には出る回数一回と戻って来る回数一回が必要である為、必ず偶数にならないといけないです。
3. 解決方法
returnするべきの文字列の変数を「impossible」で初期化します。その後、文字列が「impossible」である場合だけ検索を続けます。
一回の移動をする時kを１ずつ減少させます。（x、y）座標を下（d）、左（l）右（r）、上（u）（辞書から早い）順で優先移動するように設定します。移動する時の座標値の変化は下記のようです。
下（d）：（x＋1、y）
左（l）：（x、y−1）
右（r）：（x、y＋1）
上（u）：（x−1、y）
変化する座標を（nx、ny）と指定して、次の実行回数をk−１だとしたら、[1 ≤ nx ≤ n, 1 ≤ ny ≤ m]を満足する時（nx、ny）と（r、c）の距離を計算します。k-1 < 距離になる場合と（k-1 - 距離) % 2 != 0になる場合その移動を無視します。また、returnする文字列が「impossible」であるだけ次の移動を実行するようコードを作成したら解決します。
4. コード
public class Solution6 {
private static final String[] dname = {"d", "l", "r", "u"};
private static final int[] dx = {1, 0, 0, -1};
private static final int[] dy = {0, -1, 1, 0};
private static String answer = "impossible";
public static void main(String[] args) {
Solution6 solution6 = new Solution6();
int n = 3;
int m = 4;
int x = 2;
int y = 3;
int r = 3;
int c = 1;
int k = 5;
System.out.println(solution6.solution(n, m, x, y, r, c, k));
}
public String solution(int n, int m, int x, int y, int r, int c, int k) {
if(k < getDistance(x, y, r, c) || ((k - getDistance(x, y, r, c)) % 2 != 0)) return answer;
move(n, m, x, y, r, c, k, "");
return answer;
}
private void move(int n, int m, int x, int y, int r, int c, int k, String log){
if(k == 0){
if(x == r && y == c){
answer = log;
}
return;
}
for(int i=0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > 0 && nx <= n && ny > 0 && ny <= m){
if(k-1 < getDistance(nx, ny, r, c) || ((k-1 - getDistance(nx, ny, r, c)) % 2 != 0)) continue;
if(answer.equals("impossible")) move(n, m, nx, ny, r, c, k-1, log+dname[i]);
else return;
}
}
}
private int getDistance(int x, int y, int r, int c){
return Math.abs(x - r) + Math.abs(y - c);
}
}
Comments