백준 16956번 늑대와 양

문제

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.

출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

제한

• 1 ≤ R, C ≤ 500

 

그냥 늑대가 이동못하게 막으면 끝.

 

 

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

int R, C;
bool flag;
char arr[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };




int main(void)
{
	cin >> R >> C;
	queue<pair<int, int> > wo;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'W')
			{
				wo.push({ i,j });
			}
		}
	}

	while (!wo.empty())
	{
		int y = wo.front().first;
		int x = wo.front().second;
		wo.pop();


		for (int i = 0; i < 4; i++)
		{
			int newy = y + dy[i];
			int newx = x + dx[i];

			if (newy >= 0 && newy < R && newx >= 0 && newx < C)
			{
				if (arr[newy][newx] == '.')
				{
					arr[newy][newx] = 'D';
				}
				else if (arr[newy][newx] == 'S')
				{
					cout << 0 << endl;
					return 0;
				}
			}
		}
	}

	cout << 1 << endl;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cout << arr[i][j];
		}
		cout << endl;
	}
	

}