boj 2140 지뢰찾기

https://www.acmicpc.net/problem/2140

 

보드의 테두리에 숫자가 있고, 닫혀있는 칸들 중 지뢰가 최대 몇개 묻혀져 있는지 구하는 문제입니다.

지뢰의 최대 수를 구하면 되기 때문에 닫혀있는 칸들 중 지뢰가 아닌 칸은 숫자라고 생각하시면 되겠습니다.

 

우선 지뢰가 있으려면 주변에 0이 없어야 합니다.

8방향 탐색으로 0이 있는지 확인하시고, 0이 없다면 지뢰를 묻어주도록 합니다.

지뢰를 묻은 칸은 -1으로 변경해주고, 주변 8방향에 있는 숫자 칸들은 모두 -1을 해줍니다.

-1으로 변경해주는건 #으로 남은 칸들은 모두 숫자로 보기 때문입니다.

 

이 과정을 계속 반복해주시면 답을 구하실 수 있습니다.

 

 

#include <iostream>
#define MAX 101
using namespace std;
 
char list[MAX][MAX];
int direct[8][2] = { {1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1} };
int N;
 
void eraseNum(int x, int y) {
    for (int d = 0; d < 8; d++) {
        int nx = x + direct[d][0];
        int ny = y + direct[d][1];
        if (list[nx][ny] == -1 || list[nx][ny] == '#') continue;
        list[nx][ny] -= 1;
    }
}
 
void func() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (list[i][j] != '#') continue;
 
            bool flag = true;
            for (int d = 0; d < 8; d++) {
                int nx = i + direct[d][0];
                int ny = j + direct[d][1];
 
                if (list[nx][ny] == '0') {
                    flag = false;
                    break;
                }
            }
 
            if (flag) {
                ret++;
                list[i][j] = -1;
                eraseNum(i, j);
            }
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}