백준
백준 소스코드 [C++] 16946 벽 부수고 이동하기 4
Hani_Levenshtein
2021. 2. 19. 00:06
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이
www.acmicpc.net
백준 소스코드 [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;
}