글 읽기 - 고수님들 도와주세요 ㅜㅜ

hesue615 6년 전 0

어느 부분이 틀렸는지 잘 모르겠습니다.

대부분의 테스트 케이스는 해결이 되었는데 반례를 찾기가 어렵습니다..

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

void BFS ();
bool isInRange (int, int);
void flooding (int);

queue<pair<int, int> > q;
int visited[100][100];
int time[100][100];
char forest[100][100];
int r, c;
pair<int, int> start, target;

int main (void) {
	scanf("%d %d%*c", &r, &c);
	for (int i = 0; i < r; ++ i) {
		for (int j = 0; j <= c; ++ j) {
			forest[i][j] = getchar();
			if (forest[i][j] == 'D')  {
				target.first = i;
				target.second = j;
			} else if (forest[i][j] == 'S') {
				start.first = i;
				start.second = j;
			}
		}
	} BFS();
	if (visited[target.first][target.second]) printf("%d\n", visited[target.first][target.second]);
	else printf("KAKTUS\n");

	return 0;
}

void BFS () {
	int m = 0;
	int x, y, nx, ny;
	int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
	q.push(make_pair(start.first, start.second));
	
	while (!q.empty()) {
		x = q.front().first; y = q.front().second;
		q.pop();
		if (x == target.first && y == target.second) break;
		if (forest[x][y] == '*') continue;
		for (int i = 0; i < 4; ++ i) {
			nx = x + dx[i]; ny = y + dy[i];
			if (isInRange(nx, ny) && (forest[nx][ny] == '.' || forest[nx][ny] == 'D') && visited[nx][ny] == 0) {
				visited[nx][ny] = visited[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		} flooding(++ m);
	}
}

bool isInRange (int nx, int ny) {
	return (0 <= nx && nx < r) && (0 <= ny && ny < c);
}

void flooding (int m) {
	int x, y, nx, ny;
	int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

	for (x = 0; x < r; ++ x) {
		for (y = 0; y < c; ++ y) {
			if (forest[x][y] == '*' && time[x][y] < m) {
				time[x][y] = m;
				for (int i = 0; i < 4; ++ i) {
					nx = x + dx[i]; ny = y + dy[i];
					if (isInRange(nx, ny) && forest[nx][ny] == '.') {
						forest[nx][ny] = '*';
						time[nx][ny] = m;
					}
				}
			}
		}
	}
}

sgchoi5 6년 전 0

COCI 문제는 대회에서 사용했던 TC 가 공개되어 있으니 한 번 써보세요. : )

https://gooddaytocode.blogspot...

hesue615 6년 전 0

감사합니다..ㅜㅜ

pda_pro12 6년 전 0

주석 달아놨습니다~

#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;

struct Char {
	int x, y, cnt;
}d;

struct Flood {
	int x, y;
}e;

queue<Char> block; queue<Flood> block1;  bool Can = false;
char arr[51][51];    int visit[51][51]; int visit1[51][51];
int n, m;     int dx[] = { -1,1,0,0 };  int dy[] = { 0,0,-1,1 }; 


void Water() {   // 물이 찰지역에 고슴도치가 있으면 물로 바꿔버린다.
	int size = block1.size();
	for (int i = 0; i < size; i++) {
		int x1 = block1.front().x;
		int y1 = block1.front().y;
		visit[x1][y1] = 1; 
		block1.pop();

		for (int j = 0; j < 4; j++) {
			int nx = x1 + dx[j]; int ny = y1 + dy[j];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (arr[nx][ny] != 'D' && visit[nx][ny] == 0 && arr[nx][ny] != 'X') {
					arr[nx][ny] = '*';
					visit[nx][ny] = 1;
					e.x = nx; 
					e.y = ny; 
					block1.push(e);
				}
			}
		}
	}
}

void Start(int a, int b) {  // 고슴도치가 이동하는 함수 , 목적지에 다다르면 return 시켜준다. 인자로 목적지 좌표를 받을 필요가 있음
	int size = block.size();   
	for (int i = 0; i < size; i++) {
		int x1 = block.front().x; 
		int y1 = block.front().y; 
		int cnt1 = block.front().cnt;

		visit[x1][y1] = 1; 

		block.pop();

		if (a == x1 && b == y1) {
			cout << cnt1; 
			Can = true;
			return;
		}

		for (int j = 0; j < 4; j++) {
			int nx = x1 + dx[j]; int ny = y1 + dy[j];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (arr[nx][ny] != '*' && visit1[nx][ny] == 0 && arr[nx][ny] != 'X') {
					visit1[nx][ny] = 1; 
					d.x = nx;
					d.y = ny; 
					d.cnt = cnt1 + 1;
					block.push(d);
				}
			}
		}
	}
}

int Cycle(int a, int b) { // 목적지 좌표를 인자로 주어서 맵을 한번 쭉 훑는다.
	while (!block.empty()) {
		if (Can == true)
			break;

		Water();
		Start(a,b);
	}
	if (Can == false) {
		cout << "KAKTUS";
		return 0;
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {   // 초기 고슴도치의 위치와
			cin >> arr[i][j];
			if (arr[i][j] == 'S') {
				d.x = i;
				d.y = j;
				d.cnt = 0;
				block.push(d);
			}
			else if (arr[i][j] == '*') {  // 물의 위치를 큐에 저장
				e.x = i; 
				e.y = j;
				block1.push(e);
			}
		}
	}


	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			if (arr[i][j] == 'D') Cycle(i, j);	
	return 0;
}

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

문제

문제

출처

ICPC

고수님들 도와주세요 ㅜㅜ

hesue615 6년 전 0

sgchoi5 6년 전 0

hesue615 6년 전 0

pda_pro12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말