글 읽기 - 4179<불>과 다른로직인지 조언부탁드립니다

rlawnddnjs12 2년 전 0

4179와는 동일한 알고리즘으로 테스트 케이스의 수만 늘어난거라고 판단이 들어

그 부분만 수정하였고 4179<불>문제와 동일한 코드를 제출하였는데 계속 틀렸다고 나옵니다.

물론 행/열 바뀌는 부분 수정하고, 초기화도 한 후에 코드를 올렸습니다.

4179와 다른 문제라면 어떤 부분이 다른건지,

아니면 제 코드가 잘못되어 틀린건데 어디가 왜 틀린건지 조언 부탁드립니다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define MAX_SIZE 1003
#define MAX_SIZE_Q 100003
struct node {
	int x;
	int y;
};

int size = 0, fire = 0;

int head = 0, tail = 0;
struct node queue[MAX_SIZE_Q];

int head1 = 0, tail1 = 0;
struct node queue1[MAX_SIZE_Q];

int R, C;
char Graph[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int cnt = 1;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool flag, judge;

void enque(int x_, int y_) {
	struct node t;
	t.x = x_;
	t.y = y_;
	queue[tail] = t;
	tail = (tail + 1) % MAX_SIZE_Q;
	size++;
}

struct node deque() {
	struct node temp = queue[head];
	head = (head + 1) % MAX_SIZE_Q;
	size--;
	return temp;
}

int Is_Empty() {
	if (head == tail) {
		return 0;
	}
	else {
		return 1;
	}
}

void enque1(int x_, int y_) {
	struct node t;
	t.x = x_;
	t.y = y_;
	queue1[tail1] = t;
	tail1 = (tail1 + 1) % MAX_SIZE_Q;
	fire++;
}

struct node deque1() {
	struct node temp = queue1[head1];
	head1 = (head1 + 1) % MAX_SIZE_Q;
	fire --;
	return temp;
}

int Is_Empty1() {
	if (head1 == tail1) {
		return 0;
	}
	else {
		return 1;
	}
}

int BFS() {
	int nextX, nextY;

	int res=0;
	while (1) {
		//불부터 번지기 시작
		if (size == 0) {
			break;
		}
		int fire_e = fire;
		for (int i = 0; i < fire_e; i++) {
			struct node t = deque1();

			for (int i = 0; i < 4; i++) {
				nextX = t.x + dx[i];
				nextY = t.y + dy[i];

				if (0 <= nextX && nextX < C && 0 <= nextY && nextY < R) {
					if (visited[nextX][nextY] == 0 || visited[nextX][nextY] == 1) {
						enque1(nextX, nextY);
						visited[nextX][nextY] = 4;
					}
				}
			}
		}

		int e = size;
		for (int i = 0; i < e; i++) {
			struct node k = deque();

			if (k.x == 0 || k.x == C - 1 || k.y == 0 || k.y == R - 1) {
				flag = true;
				res = cnt;
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				nextX = k.x + dx[i];
				nextY = k.y + dy[i];

				if (0 <= nextX && nextX < C && 0 <= nextY && nextY < R) {
					if (visited[nextX][nextY] == 0) {
						enque(nextX, nextY);
						visited[nextX][nextY] = 1;
					}
				}
			}
		}
		if (flag) {
			break;
		}
		cnt++;
	}
	if (flag) {
		return res;
	}
	else {
		return -1;
	}
}


void Reset() {
	while (Is_Empty()) {
		deque();
	}
	while (Is_Empty1()) {
		deque1();
	}
	head = tail = head1 = tail1 = 0;
	flag = false;
	judge = false;
	cnt = 1;
	size = fire = 0;
	memset(visited, 0, sizeof(visited));
}

int main() {
	char tc;
	tc = getchar();
	int t = (tc - '0');
	for(int i=0;i<t;i++){
		Reset();
		scanf("%d %d", &R, &C);

		for (int x = 0; x < C; x++) {
			scanf("%s", Graph[x]);
		}

		for (int x = 0; x < C; x++) {
			for (int y = 0; y < R; y++) {
				if (Graph[x][y] == '#') {
					visited[x][y] = -1;
				}
				else if (Graph[x][y] == '.') {
					visited[x][y] = 0;
				}
				else if (Graph[x][y] == '@') {
					if (x == 0 || x == C - 1 || y == 0 || y == R - 1) {
						judge = true;
					}
					enque(x, y);
					visited[x][y] = 1;
				}
				else {
					enque1(x, y);
					visited[x][y] = 4;;
				}
			}
		}
		if (judge) {
			printf("%d\n", cnt);
		}
		else {
			int result = BFS();
			if (result < 0) {
				printf("IMPOSSIBLE\n");
			}
			else {
				printf("%d\n", result);
			}
		}
	}
	return 0;
}

rlawnddnjs12 2년 전 0

바보같은 짓을 했습니다.

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

문제

문제

출처

ICPC

4179<불>과 다른로직인지 조언부탁드립니다

rlawnddnjs12 2년 전 0

rlawnddnjs12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말