28. SW_Test 연습 백준 16946번 벽부수고 이동하기 4

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

#pragma warning (disable :4996)
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int Map[1000][1000];
int solMap[1000][1000];
int markMap[1000][1000];
bool vist[1000][1000];
int N, M;
int dir[4][2] = { {1,0} ,{-1,0}, {0,1}, {0,-1} };
vector<pair<int, int>> v;
vector<pair<int, int>> vone;
void bfs(int y,int x,int mark) {
	queue <pair<int,int>> q;
	queue <pair<int, int>> qtwo;
	q.push(pair<int, int>(y,x));
	qtwo.push(pair<int, int>(y, x));
	vist[y][x] = true;
	int cnt = 1;
	while (!q.empty()){
		int cunY =q.front().first;
		int cunX =q.front().second;
		q.pop();
		for (int i = 0; i < 4;i++) {
			int nextY = cunY + dir[i][0];
			int nextX = cunX + dir[i][1];
			if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M || vist[nextY][nextX] == true) continue;
			if (Map[nextY][nextX] == 0) {
				q.push(pair<int, int>(nextY, nextX));
				qtwo.push(pair<int, int>(nextY, nextX));
				vist[nextY][nextX] = true;
				cnt++;
			}
		}
	}
	while (!qtwo.empty()){
		solMap[qtwo.front().first][qtwo.front().second] = cnt;
		markMap[qtwo.front().first][qtwo.front().second] = mark;
		qtwo.pop();
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d %d",&N ,&M);
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Map[i][j]);
			if (Map[i][j] == 0) { v.push_back(pair<int, int>(i, j)); }
			else { vone.push_back(pair<int, int>(i, j)); }
		}
	}
	int num = 1;
	for (int index = 0; index < v.size();index++) {
		if (vist[v[index].first][v[index].second] == false) {
			bfs(v[index].first, v[index].second, num++);
		}
	}
	for (int index = 0; index < vone.size(); index++) {
		int cunY = vone[index].first;
		int cunX = vone[index].second;
		int marks[4] = { -1,-1,-1,-1 };
		int sum =1;
		for (int i = 0; i < 4; i++) {
			bool falg = false;
			int nextY = cunY + dir[i][0];
			int nextX = cunX + dir[i][1];
			if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M ) continue;
			if (solMap[nextY][nextX] == 0) continue;
			for (int j = 0;j<4;j++) {
				if (marks[j] == markMap[nextY][nextX]) {
					falg = true;
					break;
				}
			}
			if (falg == true) continue;
			sum = sum + solMap[nextY][nextX];
			marks[i] = markMap[nextY][nextX];
		}
		Map[cunY][cunX] = sum;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", Map[i][j]%10);
		}
		printf("\n");
	}
	return 0;
}