글 읽기 - 모든케이스 다맞게돌아갑니다. 모르겠습니다.

minjae200 6년 전 0

bfs로 물퍼지게하고 bfs로 고슴도치 돌렸습니다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

char map[50][50];
int dp[50][50];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int R, C;
int goX, goY, bX,bY, wX,wY;
int result = -1;
int waterloop = 0;
int goloop = 0;
bool ok = true;
queue<pair<int,int>> wq;
queue<pair<int,int>> gq;
void bfs(void)
{
	while(ok){
		int cnt = 0;
		for(int j = 0; j <waterloop; j++){
			wX = wq.front().second;
			wY = wq.front().first;
			wq.pop();
			for(int i = 0; i<4; i++)
			{
				int next_wx = wX + dx[i];
				int next_wy = wY + dy[i];
				if(0<= next_wy && next_wy < R && 0<= next_wx && next_wx <C)
				{
					if(map[next_wy][next_wx] == 'X' || map[next_wy][next_wx] == 'D') continue;
					else if(map[next_wy][next_wx] == '.' || map[next_wy][next_wx] == 'S'){
						map[next_wy][next_wx] = '*';
						cnt++;
						wq.push(make_pair(next_wy,next_wx));
					}
				}
			}
		}
		waterloop = cnt;

	/*	for(int i = 0; i<R; i++){
			for(int j = 0; j<C; j++){
				cout<<map[i][j];
			}
			cout<<endl;
		}
		cout<<endl;*/
		//고슴도치 BFS 고고
		cnt = 0;
		bool inOk = false;
		for(int j = 0; j <goloop; j++){
			int wrongcnt = 0;
			goX = gq.front().second;
			goY = gq.front().first;
			gq.pop();
			int temp = dp[goY][goX];
			for(int i = 0; i<4; i++)
			{
				int next_gx = goX + dx[i];
				int next_gy = goY + dy[i];
				if(0<= next_gy && next_gy < R && 0<= next_gx && next_gx <C)
				{
					if(map[next_gy][next_gx] == '.' || map[next_gy][next_gx] == 'D'){
						if(dp[next_gy][next_gx] != -1) continue;
						cnt++; inOk = true;
						gq.push(make_pair(next_gy, next_gx));
						dp[next_gy][next_gx] = temp+1;
						if(map[next_gy][next_gx] == 'D') return;
					}
					else if(map[next_gy][next_gx] == '*' || map[next_gy][next_gx] == 'X'){
						wrongcnt++;
					}
				}
				else{
					wrongcnt++;
				}
			}
			if(wrongcnt == 4 && inOk==false){
				return;
			}
		}
		goloop = cnt;
		if(goloop == 0) return;
	}
	return;
}

int main(void)
{
	cin>>R>>C;
	memset(dp,-1,sizeof(dp));
	for(int i = 0; i<R; i++){
		for(int j = 0; j<C; j++){
			cin>>map[i][j];
			if(map[i][j] == '*'){
				waterloop = ++waterloop;
				wq.push(make_pair(i,j));
			}
			else if(map[i][j] == 'S'){
				goloop++;
				gq.push(make_pair(i,j));
				dp[i][j] = 0;
			}
			else if(map[i][j] == 'D'){
				bX = j;
				bY = i;
			}
		}
	}
	bfs();
	if(dp[bY][bX] == -1)
		cout<<"KAKTUS"<<endl;
	else
		cout<<dp[bY][bX]<<endl;
	return 0;
}

sgchoi5 6년 전 0

정 안되시면 원래 대회의 TC 에서도 잘 되는지 한 번 해보셔요.

minjae200 6년 전 0

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

모든케이스 다맞게돌아갑니다. 모르겠습니다.

minjae200 6년 전 0

sgchoi5 6년 전 0

minjae200 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말