[白俊]#17267純爺たち

質問する

CTPの代表的な男子英祖は自由移動が好きだ.しかし永喬は男なので上下だけ.そのため、上下は自由に移動できますが、左、右に移動しません.しかし、英祖の友人の宝成は、英祖が上、下にしか行かないのを防ぐために、英祖と一緒に歩いて、英祖を左に最大L回、右に最大R回助けた.英祖と宝成は地図を出せない.
到達可能な土地、壁の位置、永喬と宝城の出発位置が地図情報に指定されている場合、永喬と宝城は出発位置から移動し、到達可能なすべての土地の個数を求める.
以下に、理解を助ける例1の図を示す.

永祚と宝城がスタート地点で歩ける場所は青、壁があって歩けない場所は黒.
次の図は、永喬と宝成がスタート位置から左に1格移動したときです.

左に一コマ移動して左には行けなくなり、現在の状態で歩く道が青に表示されます.
下の図は永喬と宝成がスタート位置から下へ歩いた時です.

永祚と宝城が1格下に移動した時の可去土地と現在の状態.
下の図は、英祖と宝城が自由に移動したときに到達できる土地を示しています.

永喬と宝成は最大で左にL回、右にR回移動し、自由に移動できる土地は13格です.

入力

1行目は地図の行と列N,M(1≦N,M≦1000)を与える.
2行目では,左と右の最大回数L,Rが与えられる.(0 ≤ L, R ≤ M)
3行目からN+2行目まで、地図の大きさはMの大きさと同じです.

0:耕地可能

1:壁があって行けない土地

2:永祚と宝城の所在地

しゅつりょく

到達可能な土地の個数を出力し、開始位置を含む.

入力例1

5 5
1 1
00000
00000
02100
10000
00000

サンプル出力1

13

入力例2

4 5
1 2
00000
11010
02011
10000

サンプル出力2

10

に答える

この問題はbfs(幅優先探索)アルゴリズムで解くことができる.最初は四次元配列で解こうと思っていましたが、メモリが大きすぎると思って引き返しました.ここで重要なのは、上、下の制限がないことです.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        int L = Integer.parseInt(input[0]);
        int R = Integer.parseInt(input[1]);

        map = new int[N][M];
        Pair start = new Pair(0, 0, L, R);

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';

                if(map[i][j]==2) {
                    start.x = i;
                    start.y = j;
                    map[i][j] = 0;
                }
            }
        }

        bfs(N, M, start);
    }

    public static void bfs(int N, int M, Pair start) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        int ans = 1;
        queue.add(start);
        visited[start.x][start.y] = true;

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = temp.x;
                int ny = temp.y;

                if(i==0) {                //상, 하로 가는 방법은 횟수 제한이 없기 때문에 막히는 곳까지 갈 수 있는 모든  큐에 넣어줌
                    while(true) {
                        nx = nx+dx[i];
                        ny = ny+dy[i];

                        if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) break;

                        visited[nx][ny] = true;
                        queue.add(new Pair(nx, ny, temp.l, temp.r));
                        ans++;
                    }
                }

                else if(i==1) {
                    while(true) {
                        nx = nx+dx[i];
                        ny = ny+dy[i];

                        if(nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) break;

                        visited[nx][ny] = true;
                        queue.add(new Pair(nx, ny, temp.l, temp.r));
                        ans++;
                    }
                }

                else if(i==2) {               //좌,우는 한 칸씩 큐에 넣어줌
                    nx = nx+dx[i];
                    ny = ny+dy[i];

                    if(temp.l==0 || nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) continue;

                    visited[nx][ny] = true;
                    queue.add(new Pair(nx, ny, temp.l-1, temp.r));
                    ans++;
                }

                else {
                    nx = nx+dx[i];
                    ny = ny+dy[i];

                    if(temp.r==0 || nx<0 || nx>=N || ny<0 || ny>=M || map[nx][ny]==1 || visited[nx][ny]) continue;

                    visited[nx][ny] = true;
                    queue.add(new Pair(nx, ny, temp.l, temp.r-1));
                    ans++;
                }
            }
        }

        System.out.println(ans);
    }

    public static class Pair {
        int x;            //행
        int y;            //열
        int l;            //왼쪽으로 갈 수 있는 횟수
        int r;            //오른쪽으로 갈 수 있는 횟수

        public Pair(int x, int y, int l, int r) {
            this.x = x;
            this.y = y;
            this.l = l;
            this.r = r;
        }
    }
}