#2140. 지뢰찾기

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

1. 문제 이해

 길이가 n인 정사각형의 맨 밖깥 부분에만 숫자가 써져 있고 그 안에는 #으로 지뢰가 가려져 있습니다. 

지뢰가 최대로 있을 경우를 구하는 문제입니다.

2. 접근 방법

 #부분을 공략하는 것이 이 문제의 point 입니다.

1. # 부분을 완전 탐색 합니다.

2. #부분의 8방향에 0이 하나라도 있다면 # 부분에는 지뢰가 없습니다.

3. #부분의 8방향이 0이 하나도 업다면 카운트를 올려주고, 주변 8방향을 -1 해줍니다.

3. 문제 해결

#include <string>
#include <iostream>
#include <vector>
#include <cstdio>
#define MAX_SIZE 105
 
using namespace std;
 
int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int map[MAX_SIZE][MAX_SIZE];
 
void find_bomb(int x, int y, int& cnt) {
    bool flag = true;        // 0이 없으면 true
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (map[ny][nx] == 0) {
            flag = false;
            break;
        }
    }
 
    if (flag) {
        cnt++;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(map[ny][nx] > 0)    map[ny][nx] -= 1;
        }
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    vector <string> input(n);
    for (int i = 0; i < n; i++) {
        cin >> input[i];
        for (int j = 0; j < n; j++) {
            map[i][j] = input[i][j] - 48;
        }
    }
    
    int cnt = 0;
 
    if (n == 3) {
        find_bomb(1, 1, cnt);
    }
    else if (n > 3) {
        for (int i = 1; i <= n - 2; i++) {
            for (int j = 1; j <= n - 2; j++) {
                find_bomb(j, i, cnt);
            }
        }
    }
 
    printf("%d\n", cnt);
 
    return 0;
}