백준 소스코드 [C++] 16946 벽 부수고 이동하기 4

www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

백준 소스코드 [C++] 16946 벽 부수고 이동하기 4

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

int n, m,h=0;
int arr[1002][1002],brr[1002][1002];
bool chk[1002][1002];
int dy[4] = { 1,0,-1,0 }, dx[4] = { 0,-1,0,1 };
int crr[500002];
struct dot {
	int y, x;
};
void bfs(dot t) {
	queue<dot> q;
	q.push(t);
	chk[t.y][t.x] = true;
	brr[t.y][t.x] = h;
	int sum = 0;
	while (q.empty() != true) {
		dot k = q.front();
		brr[k.y][k.x] = h;
		sum++;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int newy = k.y + dy[i];
			int newx = k.x + dx[i];
			if (arr[newy][newx] == 0 && chk[newy][newx] == false) {
				chk[newy][newx] = true;
				dot newdot;
				newdot.y = newy, newdot.x = newx;
				q.push(newdot);
			}
		}
	}
	crr[h] = sum;
	h++;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(arr, -1, sizeof(arr));
	cin >> n >> m;
	string s;
	for (int i = 1;i <= n;i++) {
		cin >> s;
		for (int j = 1;j <= m;j++) arr[i][j] = s[j - 1] - '0';

	}
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
		if (arr[i][j] == 0 && chk[i][j] == false) {
			dot t; t.y = i, t.x = j;
			bfs(t);
			}

	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++)
			if (arr[i][j] == 1) {
				vector<int> v;
				for (int k = 0;k < 4;k++) 
					if(arr[i + dy[k]][j + dx[k]]==0)
						v.push_back(brr[i + dy[k]][j + dx[k]]);
				sort(all(v));
				make_unique(v);
				int res = 1;
				for (auto a : v) res = res + crr[a];
				cout << res%10;
			}
			else cout << "0";
		cout << '\n';
	}
	return 0;
}