ゲームマップ最短距離

3612 ワード

問題の説明
RORゲームは2チームに分かれて行い、先に相手陣営を破壊すれば勝つゲームです.そのため、各チームはできるだけ早く相手陣営に到着したほうがいい.
これからはチームのメンバーになってゲームをします.以下に、5×5サイズのマップで、キャラクタが(行:1、列:1)、相手陣営が(行:5、列:5)の位置にある例を示します.

上図では、黒い部分は壁に塞がれて歩けない道で、白い部分は歩ける道です.キャラクターが移動するときは東、西、南、北に1コマずつ移動し、ゲームマップから離れることはできません.
次の例では、キャラクタが相手の陣営に向かう2つの方法を示します.
  • 最初の方法は11格子を経て相手陣営に到着した.
  • 第2の方法は15格子を経て相手陣営に到着する.

  • 上記の例では、第1の方法ほど相手陣営に早く到達する方法はないので、相手陣営に向かう最も速い方法である.
    相手が自分の陣営の周りに壁を立てたら、相手の陣営に届かないかもしれない.たとえば、次の場合、キャラクタは相手の陣営に到達できません.

    ゲームマップのステータスマップをパラメータとして与える場合は、solution関数を完了し、キャラクタを相手陣営が通過する必要がある格子数の最大値に戻します.でも相手陣営に届かない時は-1に戻ってください
    せいげんじょうけん
  • 地図は、n x mサイズのゲーム地図状態を含む2次元配列であり、nとmはそれぞれ1または100以下の自然数である.
  • nとmは同じでも異なっていてもよいが、nとmがともに1である場合、入力は与えられない.
  • マッピングは0と1のみで構成され、0は壁のある位置を表し、1は壁のない位置を表す.
  • 最初のキャラクターはゲームマップの左上隅(1,1)の位置にあり、相手陣営はゲームマップの右下隅(n,m)の位置にある.
  • I/O例
    mapsanswer[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]11[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]-1
    I/O例説明
    I/O例#1
    与えられたデータは次のとおりです.

    キャラクターが敵陣営に移動する最速経路を下図に示します.

    全部で11コマのキャラクターが通ったので11に戻ればいいです
    I/O例#2
    問題例と同様に,相手陣営に到達できない.したがって、-1を返します.

    私の答え


    典型的なDFS、BFSで歩ける道を探して、見つけた道の最短距離の問題を計算します
    import java.util.*;
    class Solution {
        static int[][] dirs = {{0, 1},{0, -1}, {1, 0}, {-1, 0}};
        static boolean[][] visited;
        static int[][] map;
        static int[] target;
        static int answer;
        static class Point{
            int x;
            int y;
            int cnt;
            Point(int x, int y, int cnt){
                this.x = x;
                this.y = y;
                this.cnt = cnt;
            }
        }
        static void bfs(Point point){
            Queue<Point> que = new LinkedList<>();
            que.add(point);
            while(!que.isEmpty()){
                Point pre = que.poll();
                // if(pre.cnt > answer) continue;
                if(pre.x == target[0] && pre.y == target[1]){
                    answer = Math.min(pre.cnt, answer);
                    return;
                }
                for(int dir = 0; dir < 4; dir++){
                    int nr = pre.x + dirs[dir][0];
                    int nc = pre.y + dirs[dir][1];
                    if(nr >= 0 && nr < map.length && nc >= 0 && nc < map[0].length && !visited[nr][nc] && map[nr][nc] == 1){
                        Point next = new Point(nr, nc, pre.cnt + 1);
                        visited[nr][nc] = true;
                        que.add(next);
    
                    }
                }
            }
        }
        public int solution(int[][] maps) {
    
            answer = maps.length * maps[0].length + 1;
            map = maps.clone();
            visited = new boolean[maps.length][maps[0].length];
            target = new int[2];
            target[0] = maps.length-1;
            target[1] = maps[0].length -1;
    
            bfs(new Point(0,0,1));
            if(answer == maps.length * maps[0].length+1){
                answer = -1;
            }
            return answer;
        }
    
    }