글 읽기 - 어디가 틀렸는지 모르겠습니다 도와주세요 ㅠㅜ

seongjina 4년 전 0

예제를 다 맞았고, 질문게시판에 있는 반례들 다 해봤는데 계속 틀렸습니다 뜹니다 ㅜㅠ

혹시 도와주실수있으신가요??

정말 풀고싶습니다 ㅜㅠ

#include <stdio.h>

typedef struct {
	int x, y;
}Position;

int n, m;
int spread; // 퍼뜨려야할 개수
int map[55][55];
int virus[15][2];
int res[15][2];
int vCount;
int smallTime = 2500;

Position queue[55 * 55];
int front, back;

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

void EnQueue(int x, int y) {
	Position news;
	news.x = x;
	news.y = y;

	queue[back++] = news;
	return;
}

Position DeQueue() {
	return queue[front++];
}

void dfs(int idx, int num) {
	res[idx][0] = virus[num][0];
	res[idx][1] = virus[num][1];

	//만약 idx == m 이라면 확산되기
	if (idx == m) {
		int visited[55][55] = { 0 };
		int count = 0;
		int time = 0;
		front = 0, back = 0;
		for (int i = 1; i <= m; i++) {
			EnQueue(res[i][0], res[i][1]);
			visited[res[i][0]][res[i][1]] = 100;
		}

		while (front != back) {
			Position current = DeQueue();
			int x = current.x;
			int y = current.y;
			for (int i = 0; i < 4; i++) {

				int xx = x + drt[i][0];
				int yy = y + drt[i][1];

				//범위에서 벗어날 때
				if (xx < 1 || xx > n || yy < 1 || yy > n) continue;
				//벽일 때
				else if (map[xx][yy] == 1) continue;
				//빈칸일 때
				else if (map[xx][yy] == 0) {
					//이미 퍼진 곳
					if (visited[xx][yy] >= 1) continue;
					//아직 안퍼진 곳
					else if (visited[xx][yy] == 0) {
						EnQueue(xx, yy);
						//활성 바이러스에서 퍼질 때
						if (visited[x][y] == 100) visited[xx][yy] = 1;
						//그냥 칸에서 퍼질 때
						else visited[xx][yy] = visited[x][y] + 1;
						count++;

						if (count == spread) {
							if (smallTime > visited[xx][yy]) 
								smallTime = visited[xx][yy];

							return;
						}
					}
				}
				//바이러스 위치일 때
				else if (map[xx][yy] == 2) {
					//활성 바이러스였다면
					if (visited[xx][yy] == 100) continue;
					//비활성바이러스라면
					else {
						EnQueue(xx, yy);

						//활성바이러스에서 퍼질 때
						if (visited[x][y] == 100) visited[xx][yy] = 1;
						//그냥 칸에서 퍼질 때
						else visited[xx][yy] = visited[x][y] + 1;
					}
				}


				if (visited[xx][yy] > time) time = visited[xx][yy];

				if (count == spread) {
					if (smallTime > time) smallTime = time;
					return;
				}
			}
		}

		//아직 다 퍼지지 못함! => 그냥 return smalltime이 변하지 않는다!!
		return;
	}


	//아직 남았으니 dfs 더 진행
	for (int i = num + 1; i <= vCount - m + idx + 1; i++) {
		dfs(idx + 1, i);
	}
	return;
}


int main(void)
{
	scanf("%d %d", &n, &m);

	spread = n * n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);

			if (map[i][j] == 2) {
				virus[++vCount][0] = i;
				virus[vCount][1] = j;
				spread--;
			}
			else if (map[i][j] == 1) spread--;
		}
	}
	if (spread == 0) {
		puts("0");
		return 0;
	}


	for (int i = 1; i <= vCount - m + 1; i++) {
		dfs(1, i);
	}

	if (smallTime == 2500) puts("-1");
	else printf("%d\n", smallTime);

	return 0;
}

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다 도와주세요 ㅠㅜ

seongjina 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말