글 읽기 - 고수님들 도와주세요

iopell2007 3년 전 0

벽세우는 부분은 브루트포스로 실행하고

각 케이스에서 바이러스가 퍼지는 부분은 재귀함수를 썼습니다

여러가지 반례를 만들어서 넣어보았는데, 적당한 반례를 못 찾았습니다..

어느 부분이 잘못된건가요?

#include <stdio.h>

int map[16][16];
int map_case[16][16];
int viruses[128];

void spread(int i, int j, int n, int m)
{
    map_case[i][j] = 2;
    
    if(i > 0 && map_case[i - 1][j] == 0)
        spread(i - 1, j, n, m);
    
    if(i < n - 1 && map_case[i + 1][j] == 0)
        spread(i + 1, j, n, m);
    
    if(j > 0 && map_case[i][j - 1] == 0)
        spread(i, j - 1, n, m);
    
    if(j < m - 1 && map_case[i][j + 1] == 0)
        spread(i, j + 1, n, m);
}

int get_safe_places(int virus_cnt, int n, int m)
{
    int i, j;
    int count = 0;
    
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            map_case[i][j] = map[i][j];
    
    // 바이러스 퍼트리기
    for(i = 0; i < virus_cnt; i++)
        spread(viruses[2 * i], viruses[2 * i + 1], n, m);
    
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            if(map_case[i][j] == 0)
                count++;
    
    return count;
}

int main()
{
    int n, m;
    int i, j, k;
    int virus_cnt = 0;
    int ret = 0, tmp;
    
    scanf("%d %d", &n, &m);
    
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < m; j++)
        {
            scanf("%d", &(map[i][j]));
            if(map[i][j] == 2)
            {
                viruses[2 * virus_cnt] = i;
                viruses[2 * virus_cnt + 1] = j;
                virus_cnt++;
            }
        }
    }
    
    // 벽세우기
    for(i = 0; i < n * m; i++)
    {
        if(map[i / m][i % m]) continue;
        map[i / m][i % m] = 1;
        
        for(j = i + 1; j < m * m; j++)
        {
            if(map[j / m][j % m]) continue;
            map[j / m][j % m] = 1;
            
            for(k = j + 1; k < n * m; k++)
            {
                if(map[k / m][k % m]) continue;
                map[k / m][k % m] = 1;
                
                // 안전한 영역 계산
                tmp = get_safe_places(virus_cnt, n, m);
                if(ret < tmp) ret = tmp;
                
                map[k / m][k % m] = 0;
            }
            
            map[j / m][j % m] = 0;
        }
        
        map[i / m][i % m] = 0;
    }
    
    printf("%d\n", ret);
    return 0;
}

pichulia 3년 전 2

74번째 줄을 보세요

iopell2007 3년 전 0

아 너무 어처구니없는 실수를 했네요.. 감사합니다 ㅋㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들 도와주세요

iopell2007 3년 전 0

pichulia 3년 전 2

iopell2007 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말