[백준 16946]벽 부수고 이동하기 4

문제 https://www.acmicpc.net/problem/16946

1)문제분류

-BFS

2)문제해결

- 각 정점에서 개수를 세려고하면 시간초과가 나기 때문에 다른 방법을 생각해봐야한닷.

- 인접해있는  0끼리 숫자를 세며 묶어준다.

- 그러면 묶여있는 0들 기준으로 사방에 벽인 지점을 찾아 값을 더해준다.

 이렇게 묶음을 만들고..                                                                                                     

묶음 기준으로 4방향에 1이 있다면 , 0의 개수 더하기

#include<iostream>

#include<queue>

#include<algorithm>

using namespace std;

char map[1002][1002];

int result[1002][1002];

int chk[1002][1002];

int n, m;

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

typedef struct Data

{

int x, y;

}Data;

bool range(int rx, int ry)

{

if (rx<0 || ry<0 || rx>n - 1 || ry>m - 1)return false;

else return true;

}

void search(int x, int y)

{

int cnt = 1;

chk[x][y] = true;

queue<Data>pq;

queue<Data>pq2;

pq.push({ x,y });

pq2.push({x,y });

while (!pq.empty())

{

Data output = pq.front();

pq.pop();

for (int i = 0; i < 4; i++)

{

Data input;

input.x = output.x + xrr[i];

input.y = output.y + yrr[i];

if (range(input.x, input.y) && chk[input.x][input.y] == false && map[input.x][input.y] == '0')

{

chk[input.x][input.y] = true;

cnt++;

pq.push({ input.x,input.y });

pq2.push({ input.x,input.y });

}

}

}

bool chk2[1002][1002] = { 0, };

while (!pq2.empty())

{

Data output = pq2.front();

pq2.pop();

for (int i = 0; i < 4; i++)

{

Data input;

input.x = output.x + xrr[i];

input.y = output.y + yrr[i];

if (range(input.x, input.y) && map[input.x][input.y] == '1'&&chk2[input.x][input.y]==false)

{

result[input.x][input.y] += cnt;

chk2[input.x][input.y] = true;

}

}

}

}

int main()

{

cin >> n >> m;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

scanf(" %c",&map[i][j]);

if(map[i][j]=='1')

result[i][j] = 1;

}

}

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (map[i][j] == '0'&&chk[i][j]==false)

{

search(i,j);

}

}

}

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

printf("%d",result[i][j]%10);

}

printf("\n");

}

}