[白俊]2573号:氷山

2573号:氷山

氷山は毎年溶けます.

氷山の高さ

この格の東西南北4方向の0人格の数は減少した.

セグメントで、1つのストレージの高さは0よりも減少しません.

氷山:

東西南北に連なる非零格が氷山を構成している.

必要:

氷山[2つ以上の分離の最初の時間]を求めるプログラム

は、全てが溶融前に、2つ以上が分離していなければ、出力0は

となる.

:行(N)、列(M)

NおよびMは3または300以下の

である.

問題を解く

(00:45)

ツリーの個数を求めて戻り関数を作成する

初期化のアクセスを行います.

はすべて、&&ではなく→0にナビゲートし、アクセスされていないセルに対してDFS→遍歴したセルをvisitでチェックします.

cntが2になった瞬間stopは、2を返します.

も最初はこれを処理していました.

年ごとに氷山が溶けます.

板を2枚ください.

nextはpreに基づいて作成されます.(nextはnextに基づいてはならない.

ここで、2から溶融に関する処理を開始すると、→nextは0となる.
処理4の溶融時にnextをベースにすれば4の西も0であるので4から3を減算する.

しかし、これでは1回に最大9万個のコピーが必要になります.

ああそれもいい氷河の高さは最大10なので.

9万くらいコピーして、100回くらいコピーしてもいいです.
氷山が溶けたらやるべきこと

グラフィック数を求める関数の起動
→0の場合、→stop&0を出力します.
→2の場合→年数を出力します.

package coding;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    public static int n,m;
    public static int[][] dirs=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public static int[][] board;
    public static boolean[][] visit;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException{
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        visit = new boolean[n][m];
        for(int r=0;r<n;r++){
            st = new StringTokenizer(br.readLine());
            for(int c=0;c<m;c++){
                board[r][c] = Integer.parseInt(st.nextToken());
            }
        }
    }
    public static int solve() {
        int cnt=0; // 빙산 개수
        int y=0; // 년도
        int[][] next = new int[n][m];
        // next를 pre에서 복사한다.
        copy(next,board);
        while(true) {
            cnt = evalCnt(board);
            if (cnt == 0) return 0;
            else if (cnt>=2) return y;
            // 녹는다 -> 녹은 결과가 next에.
            melt(board,next);
            // board를 next로 업데이트
            copy(board,next);
            y++;
        }
    }
    public static void melt(int[][] cb,int[][] next){
        int nr=0,nc=0;
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                // 빙산인 [r][c]에 대해서만
                if(cb[r][c]<=0)continue;
                for(int dir=0;dir<dirs.length;dir++){
                    nr = r+dirs[dir][0];
                    nc = c+dirs[dir][1];
                    //범위 넘으면 패스
                    if(nr<0||nc<0||nr>=n||nc>=m)continue;
                    // 그냥 음수가 될 수도 있게 해주었다.
                    if(cb[nr][nc]<=0)next[r][c]--;
                }
            }
        }
    }
    public static void copy(int[][] next,int[][] cb){
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                next[r][c]=cb[r][c];
            }
        }
    }
    //cb: current board
    // evaluate the number of trees
    // 0 보다 큰 칸이 아무것도 없는 경우 == 빙산이 모두녹은 경우 -> return 0
    public static int evalCnt(int[][] cb){
        int cnt=0;
        // visit array init
        for(int r=0;r<n;r++)Arrays.fill(visit[r],false);

        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                if(visit[r][c]==false&&cb[r][c]>0){
                    cnt++;
                    visit[r][c]=true;
                    dfs(r,c,cb);
                }
                if(cnt>=2)break;
            }
        }
        return cnt;
    }

    public static void dfs(int r, int c,int[][] cb){
        int nc=0,nr=0;
        for(int dir=0;dir<dirs.length;dir++){
            nr = r + dirs[dir][0];
            nc = c + dirs[dir][1];
            if(nr<=0||nc<=0||nr>=n||nc>=m) continue;
            //빙산이 아니면 패스
            if(cb[nr][nc]<=0)continue;
            //이미 방문했으면 패스
            if(visit[nr][nc])continue;
            // 방문 처리해준다.
            visit[nr][nc]=true;
            dfs(nr,nc,cb);
        }
    }
    public static void main(String[] args) throws IOException {
        setting();
        int y = solve();
        System.out.println(y);
    }
}

ミス

私の墓を掘った場所
負数に設定しました.
したがって、<=0を検証する必要がある場所もあれば、=0を使用してエラーを検証し続けない場所もあります.