글 읽기 - 문제 힌트를 좀 얻고 풀어보았는데 반례가 발생하는 것 같습니다 ㅠㅠ

gktgnjftm 5년 전 0

특정위치 (x,y)를 오는데 4방향으로 접근이 가능하기 때문에, 3차원 배열을 이용해서, 문제를 접근했습니다.

그런데, 벽을 만나거나, 이미 방문이 되어있거나, 벽을 벗어난 위치면 더이상 확장할 필요가 없기 때문에 종료해주었습니다.

반례를 만들려고 몇개만 해보기는 했는데, 잘 안보입니다 ㅠㅠ

반례 데이터나 , 풀이 올려주시면 감사하겠습니당 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
#include <stack>
using namespace std;
typedef long long ll;
#define mod 1000000009
#define lim 1000000000
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> PP;
typedef pair<pair<int, int>, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0 };
int goy[4] = { 1,0,0,-1 };
int n, m, k, sx, sy, ex, ey;
char board[1001][1001];
int dist[1001][1001][4];
bool visited[1001][1001][4];
int bfs(int x, int y, int dir) {
	queue<PP> q;
	q.push({ { x,y },dir });
	memset(visited, false, sizeof(visited));
	memset(dist, 0, sizeof(dist));
	visited[x][y][dir] = true;
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int dir = q.front().second;
		if (x == ex && y == ey) {
			int ans = 1e9;
			for (int i = 0; i < 4; i++) {
				if (dist[x][y][i] == 0) continue;
				else ans = min(ans, dist[x][y][i]);
			}
			return ans;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			for (int j = 1; j <= k; j++) {
				int nx = x + j * gox[i];
				int ny = y + j * goy[i];
				if (nx<1 || nx>n || ny<1 || ny>m || visited[nx][ny][i] || board[nx][ny] == '#') break; // 더이상 확장이 불가능하므로 종료
				else if (!visited[nx][ny][i]) {
					visited[nx][ny][i] = true;
					q.push({ { nx,ny }, i });
					dist[nx][ny][i] = dist[x][y][dir] + 1;
				}
			}
		}
	}
	return -1;
}
int main(void) {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &board[i][j]);
		}
	}
	scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
	int ans = 1e9;
	for (int i = 0; i < 4; i++) {
		ans = min(ans, bfs(sx, sy, i));
	}
	printf("%d\n", ans);
	return 0;
}

eldpswp99 4년 전 0

만약 확장하는 중간에 방문한 곳이 있어도 계속 확장해 주어야 합니다.

예를 들어, 다른방향에서 방문을 해서 만약 방문여부가 OOXOO이면 제일 왼쪽에서 오른쪽가지 확장되어야 최단경로가 나오기 때문에 확장이 멈추는 조건은 크기를 벗어나거나 벽을 만나는 것으로 제한을 해야합니다.

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

문제

문제

출처

ICPC

문제 힌트를 좀 얻고 풀어보았는데 반례가 발생하는 것 같습니다 ㅠㅠ

gktgnjftm 5년 전 0

eldpswp99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말