글 읽기 - 이 예제가 왜 안되는지 모르겠습니다..

o3oppp 4년 전 0

visit 배열에 현재까지의 명령어 횟수를 저장하여 주고

다음에 방문해야하는 곳의 visit 배열에 있는 명령어 횟수보다 현재의 명령어 횟수가 적으면 큐에 넣어 bfs를 진행하였습니다

그런데 아래의 예제가 되지않습니다..

4 2
0 0
0 0
1 0
0 0
1 1 3
4 1 3

답은 7이지만 저는 8이나옵니다

왜 안되는지를 모르겠습니다..다른분들의 코드를 참고하여 단순히 visit배열을 방문체크 여부로만 해봐도 되질않네요..

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef struct {
	int x, y, dir, cnt;
}info;
info I;
queue<info> q;
int map[101][101];
int visit[101][101][5];
int dx[5] = { 0,0,0,1,-1 };
int dy[5] = { 0,1,-1,0,0 };
int start_x, start_y, start_dir, dest_x, dest_y, dest_dir;
int m, n, result = 987654321;
void bfs() {
	int x, y, nx, ny, dir, cnt;
	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		dir = q.front().dir;
		cnt = q.front().cnt; q.pop();
		if (x == dest_x && y == dest_y && dir == dest_dir) {
			result = min(result, cnt);    //최소값 찾기
			continue;
		}
		for (int i = 1; i < 4; i++) {    //go 1,2,3
			nx = x + (dx[dir] * i);
			ny = y + (dy[dir] * i);
			if (0 < nx && nx <= m && 0 < ny && ny <= n) {
				if (!map[nx][ny] && (!visit[nx][ny][dir] || visit[nx][ny][dir] > cnt + 1)) {
					I = { nx,ny,dir,cnt + 1 };
					q.push(I);
					visit[nx][ny][dir] = cnt + 1;
				}
				else break;
			}
			else break;
		}
		for (int i = 1; i < 5; i++) {    //방향 돌리기
			if (i != dir) {
				if ((!visit[x][y][i] || visit[x][y][i] > cnt + 2) && ((dir == 1 && i == 2) || (dir == 2 && i == 1) || (dir == 3 && i == 4) || (dir == 4 && i == 3))) {
					I = { x,y,i,cnt + 2 };
					q.push(I);
					visit[x][y][i] = cnt + 2;
				}
				else if (!visit[x][y][i] || visit[x][y][cnt + 1] > cnt + 1) {
					I = { x,y,i,cnt + 1 };
					q.push(I);
					visit[x][y][i] = cnt + 1;
				}
			}
		}
	}
}
int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];
	cin >> start_x >> start_y >> start_dir;
	cin >> dest_x >> dest_y >> dest_dir;
	I = { start_x,start_y,start_dir,0 };
	q.push(I);
	visit[start_x][start_y][start_dir] = 1;
	bfs();
	cout << result;
}

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

문제

문제

출처

ICPC

이 예제가 왜 안되는지 모르겠습니다..

o3oppp 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말