[백준 16956] 늑대와 양

분류 

구현

요구사항

양에게 늑대가 접근하지 못하도록 벽 쌓기

 

풀이

모든 빈칸에 벽을 쌓아보고 늑대가 양에게 접근할 수 있는지 판단한다

위 경우, 양 바로 옆에 늑대가 있는 경우에만 접근이 가능하다

 

#include <string>
#include <vector>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;
struct go{
	int x;
	int y;
};
int n,m;
char map[501][501];
vector<go> v;
int dr[4] = {-1,0,1,0};
int dc[4] = {0,-1,0,1};
int main(){
	scanf("%d%d",&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]=='W'){
				v.push_back({i,j});
			}
		}
	}
	for(int i=0 ; i < n ; i++){
		for(int j=0 ; j <m ; j++){
			if(map[i][j]=='.'){
				map[i][j]='D';
			}
		}
	}
	int flag=0;
	for(int i=0 ; i <v.size(); i++){
		int r = v[i].x;
		int c = v[i].y;
		for(int j=0 ; j <4; j++){
			int nr = r+dr[j];
			int nc = c+dc[j];
			if(nr<0 || nc<0 || nr>=n || nc>=m) continue;
			if(map[nr][nc]=='S')
			{
			//	cout<<"nr"<<nr<<" "<<nc<<endl;
				flag=1;
				break;
			}
		}
		if(flag==1) break;
	}
	
	if(flag==0){
		cout<<"1"<<endl;
		for(int i=0 ; i < n ; i++){
			for(int j=0 ; j <m ; j++){
				cout<<map[i][j];
			}
			cout<<endl;
		}
	}
	else{
		cout<<"0"<<endl;
	}
}