[백준 2140] 지뢰찾기 (C++)

문제 링크: https://www.acmicpc.net/problem/2140

2140번: 지뢰찾기

1. 주의할 점

- Queue를 이용해서 매번 검사할 경우 -> TLE 발생

- (N-2)*(N-2)형태의 중앙에 있는 정사각형의 경우 무조건 지뢰가 있다고 가정하고 나머지 경우에서 뺀다

- N이 2이하인 경우 지뢰는 항상 없다->(처리 안해주면 100%에서 틀린다)

 

2. 구현

- 해당 칸 주위에 0이 있는 경우 -> 지뢰없음으로 결과에서 1뺀다

- 없을 경우 -> 지뢰로 여긴다 -> 주위의 숫자중 1이상인 경우 1씩 감소한다 

#include <iostream>
#include <string>
using namespace std;
int arr[100][100];		//지뢰가 없는 칸:0, 지뢰가 있는 칸: 9
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };

int main() {
	int num;
	string str;
	char c;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> str;
		for (int j = 0; j < num; j++) {
			c = str[j];
			if (c == '#') arr[i][j] = -1;
			else arr[i][j] = str[j] - '0';			
		}
	}
	int result = 0;
	if (num>2) {
		result = (num - 2)*(num - 2);
		for (int i = 1; i < num - 1; i++) {
			for (int j = 1; j < num - 1; j++) {
				if (arr[i][j] == -1) {
					bool mine = true;
					for (int k = 0; k < 8; k++) {
						int nx = j + dx[k];
						int ny = i + dy[k];
						if (arr[ny][nx] == 0) {
							mine = false;
							result--;
							break;
						}
					}
					if (mine) {
						for (int k = 0; k < 8; k++) {
							int nx = j + dx[k];
							int ny = i + dy[k];
							if (0 < arr[ny][nx] && arr[ny][nx] < 9)
								arr[ny][nx]--;
						}
					}
				}
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}