2638-チーズ-DFS

質問する

質問リンク:https://www.acmicpc.net/problem/2638

ポリシー

チーズの内部空間と外部空間を区別した.この問題では、四角い紙の最端にチーズを置かないと仮定し、この4つの部分に基づいてチーズの外部空間と内部空間を区別することができる.

チーズが室内空気と接触して少なくとも2つの変異相がある場合、1時間以内に融解し、各チーズがどのように空気と接触しているかを見つける必要がある.

この問題は、チーズを順番に除去すると、突然ない外部空間が発生するため、問題は間違っているということです.チーズ除去に関する情報は1つの配列に格納し、一括除去する必要があります.

コード#コード#

#include<bits/stdc++.h>

using namespace std;

int N, M;
int a[102][102];
// 치즈를 줄이는 것에 대한 정보를 저장한 배열
int adjustA[101][101];
// 치즈의 내부와 외부를 구별해주는 배열
int ch[102][102] = {false,};
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

// ch배열에 치즈 내부에는 1, 외부에는 -1을 넣어준다.
// value는 처음 시작하는 값이 외부인지 내부인지 알려준다. 
void findInterior(int r, int c, int value){
    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
        if(ch[rr][cc] == 0 && a[rr][cc] == 0){
            ch[rr][cc] = value;
            findInterior(rr,cc, value);
        }
    }
}

int afterHour(){
    memset(adjustA, 0, sizeof(adjustA));
    // 한시간 뒤에 치즈를 어떻게 빼줘야 할지에 대한 정보를 저장하는 과정
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(a[i][j] == 1){
                int cnt = 0;
                for(int k=0; k<4; k++){

                    int ii = i+dy[k];
                    int jj = j+dx[k];

                    if(a[ii][jj] == 0 && ch[ii][jj]==-1) cnt++;
                }
                if(cnt>=2) adjustA[i][j] = 1;
            }
        }
    }
    int res = 0;
    // 치즈를 뺴주는 과정
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            a[i][j] = a[i][j] - adjustA[i][j];
            res += a[i][j];
        }
    }
    // 남아있는 치즈의 개수가 0인지 아닌지 return해줌
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    memset(a, -1, sizeof(a));
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cin >>a[i][j];
        }
    }
    int result = 1;
    while(1){
        
        memset(ch, 0, sizeof(ch));
        
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
            	// 치즈가 아닌 외부 또는 내부 부분일때
                if(a[i][j] == 0){
                    // 치즈가 놓이지 않는 가장자리 부분에서부터 치즈 외부공기에 대한 영역을 시작한다. 
                    if((i==1 && j == 1) || (i==N && j==1) || (i==1 && j==M) || (i==N && j==M)){
                        findInterior(i,j, -1);
                    }
                    // 그 외는 모두 내부부분이다. 
                    else{
                        findInterior(i,j, 1);
                    } 
                }
                
            }
        }
        // 남아있는 치즈의 개수가 0이면 끝
        if(afterHour() == 0) break;
        result++;
    }
    cout<<result<<endl;

    return 0;
}

感想

領域の内部と外部を区別することがこの問題に深い印象を残した.格子配列をInt型にして、内部を1、外部を1、互いに区別して、内部か外部か分からない部分を0にするのが重要な部分です.また、李氏も同様に、チーズを順次除去すると、突然外部の状況が発生するため、除去すべき情報を別途保存し、チーズを統一的に除去する必要がある.