글 읽기 - [17836] 어디가 잘못된걸까요?

jeongbeen 3년 전 0

그람을 얻기 전에는 방문 체크를 visit[][][0]에서 해주었고,

그람을 얻은 후에는 방문 체크를 visit[][1]에서 해주었습니다.

bfs로 풀었습니다...

어디가 잘못된 걸까요?ㅠㅠ 반례를 찾습니다.

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
typedef pair<int, int> pi;

typedef struct {
	int x;
	int y;
	int wall; //벽을 부수었는지 확인하는 변수
	int time; //지금까지 걸린 시간
}node;
int arr[105][105];
int visit[105][105][2];
queue<node>q;
int n, m, t;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

bool outrange(int x, int y) {
	if (x <= 0 || y <= 0 || x > n || y > n) return 1;
	return 0;
}

void bfs() {
	//1,1에서 시작하므로
	visit[1][1][0] = 1;
	q.push({ 1,1,0,0 });

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int time = q.front().time;
		int wall = q.front().wall;
		q.pop();

		if (arr[x][y] == 2) { //그람을 얻은 순간
			wall = 1;
			visit[x][y][wall] = time; 
		}

		if (time > t) continue; //시간이 오바된 경우는 그냥 넘어간다
		if (x == n && y == m) { //도착
			printf("%d", time);
			return;
		}

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (outrange(nx, ny)) continue;
			if (visit[nx][ny][wall] > 0) continue; 

			if (wall == 1) { //그람을 얻은 후에는 어디든 갈 수 있다
				visit[nx][ny][wall] = time + 1;
				q.push({ nx,ny,wall,time + 1 });
			}

			else { //그람을 얻기 전에는 벽은 통과하지 못함
				if (arr[nx][ny] == 1) continue;
				visit[nx][ny][wall] = time + 1;
				q.push({ nx,ny,wall,time + 1 });
			}

		}
	}
	printf("Fail");
	return;
}

int main() {
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}
	bfs();
}

newdeal 3년 전 0

21번줄에 y>n 을 y>m 으로 고쳐야 할 것 같습니다.

jeongbeen 3년 전 0

세상에... 왜 이걸 못봤지... 정말 감사합니다 ㅠㅠㅠ

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

문제

문제

출처

ICPC

[17836] 어디가 잘못된걸까요?

jeongbeen 3년 전 0

newdeal 3년 전 0

jeongbeen 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말