아직 계정이 없으신가요? 회원가입

Dev. Talk

동계 테스트 시점 예측 오답

회원사진iwbap0110
60 views2021-11-05 20:46

동계 테스트 시점 예측에서 테스트 세트하나가 오답입니다.


외부 공기 설정하는 알고리즘이 맞는건지 모르겠습니다.


확인 부탁드립니다.

#include <stdio.h>

#define N_MAX 100
#define M_MAX 100

int N, M = 0;
int totalIce = 0;
int meltingIce = 0;
int Map[N_MAX][M_MAX] = {0};
int MeltMask[N_MAX][M_MAX] = {0};
int Count = 0;

void ResetAir(int x, int y,  int map[][M_MAX]);
void FindOutsideAir(int x, int y, int map[][M_MAX]);
int FindMeltingIce(int map[][M_MAX], int melt[][M_MAX]);
void UpdateMeltedIce(int map[][M_MAX], int melt[][M_MAX]);


int main()
{      

    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%d", &Map[i][j]);
            if(Map[i][j] == 1)
            {
                totalIce += 1;
            }
        }
    }

    while(1)
    {
        FindOutsideAir(0, 0, Map);
        meltingIce = FindMeltingIce(Map, MeltMask);
        totalIce -= meltingIce;
        Count += 1;

        if(totalIce <= 0)
        {
            break;
        } 

        UpdateMeltedIce(Map, MeltMask);
        ResetAir(0, 0, Map);
    }

    printf("%d", Count);
}

void FindOutsideAir(int x, int y, int map[][M_MAX])
{
    int nx, ny;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1}; 

    map[x][y] = -1;

    for(int a = 0; a < 4; a++)
    {
        nx = x + dx[a];
        ny = y + dy[a];

        if(nx < 0 || nx >= N || ny < 0 || ny >= M)
            continue;
        
        if(map[nx][ny] == 0)
        {
            FindOutsideAir(nx, ny, map);
        }
    }
}

void ResetAir(int x, int y, int map[][M_MAX])
{
    int nx, ny;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1}; 

    map[x][y] = 0;

    for(int a = 0; a < 4; a++)
    {
        nx = x + dx[a];
        ny = y + dy[a];

        if(nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1)
            continue;
        
        if(map[nx][ny] == -1)
        {
            ResetAir(nx, ny, map);
        }
    }
}

int FindMeltingIce(int map[][M_MAX], int melt[][M_MAX])
{
  
    int kx, ky;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1}; 
    int totalmeltingice = 0;

    for(int i = 1; i < N - 1; i++)
    {
        for(int j = 1; j < M - 1; j++)
        {
            int meltFlag = 0;
            melt[i][j] = 0;

            if(map[i][j] == 1)
            {
                for(int k = 0; k < 4; k++)
                {
                    kx = i + dx[k];
                    ky = j + dy[k];

                    if(map[kx][ky] == -1)
                    {
                        meltFlag += 1;
                    }
                    
                    if(meltFlag >= 2)     
                    {
                        melt[i][j] = 1;
                        totalmeltingice += 1;
                        break;
                    }
                }
            }      
        }
    }
    
    return totalmeltingice;
}

void UpdateMeltedIce(int map[][M_MAX], int melt[][M_MAX])
{
    int total;

    for(int i = 1; i < N - 1; i++)
    {
        for(int j = 1; j < M - 1; j++)
        {
            map[i][j] -= melt[i][j];
        }
    }
}