글 읽기 - 1600 질문 드립니다 64%쯤에서 틀렸습니다가 나옵니다......

axa1239 4년 전 0

예제 입력과 여러 가지 반례들을 대입 시켜 봤을 땐 문제 없이 정답이 나옵니다..

하지만 64% 쯤에서 틀렸습니다가 나옵니다

접근 방식은 이러 합니다

BFS 를 이용 하였고 3차원 배열을 이용하여 3차원 배열에 스킬을 사용 할 수 있는횟수를 다 같이 저장하여 최소 횟수를 구하였습니다.

이동 할 때마다 만약에 스킬을 사용 한다면 다음칸에다가 현재 사용 할 수 있는 스킬의 수를 빼고 다음칸에 저장을 하였습니다

그냥 인접한 칸을 이동 한다면 그대로 저장을 하였습니다 또한 현재 사용 할 수 있는 스킬이 0개 라면 인접한 칸만을 이동 하게 끔 코드를 구성 하였습니다

이해 하기가 쉽게끔 최대한 코드에다가 주석을 달아 놓았습니다..

왠만한 반례를 구성하여 실험 해보고 게시판에 올라온 반례또한 실험 해보았지만 틀렸습니다가 나옵니다

조언좀 부탁 드릴게요!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;

const int MAX = 200;
const int dx[] = { -1, 0, 1, 0, -1, -2, -2, -1, 1, 2, 2, 1 };
const int dy[] = { 0, 1, 0, -1, 2, -1, 1, 2, 2, 1, -1, -2 };
int dist[MAX][MAX][MAX];

int k, w, h;

// 이동 하였을 때 맵의 범위를 벗어 나진 않는지 검사 한다.
bool isInRange(int x, int y) {
	if (0 <= x && x < h && 0 <= y && y < w) return true;
	else return false;
}

int main() {

	cin >> k >> w >> h;
	vector<vector<int>> map(h, vector<int>(w));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
		}
	}
    
	memset(dist, -1, sizeof(dist));
	queue <tuple <int, int, int >> q;
	dist[0][0][k] = 0;
	q.push({ 0, 0, k });
	while (!q.empty()) {
		int x, y, s;
		tie(x, y, s) = q.front();
		q.pop();
	
		for (int i = 0; i < 12; i++) {
			if (i >= 4 && s <= 0) break;
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (isInRange(nx, ny) == false) continue;
			if (map[nx][ny] == 1) continue;

			// i < 4 부분은 인접 한 칸을 이동 할 수 있다.
			if (i < 4 && dist[nx][ny][s] == -1) {
				q.push({ nx, ny, s });
				dist[nx][ny][s] = dist[x][y][s] + 1;
			}
			// 말로 이동 할 수 있는 횟수가 0이 아니라면 말로 이동 할 수 있다는 뜻이다.! 말로 이동 가능!
			else if (i >= 4 && dist[nx][ny][s - 1] == -1) {
				q.push({ nx, ny, s - 1 });
				dist[nx][ny][s - 1] = dist[x][y][s] + 1;
			}
		}
	}
	int ans = -1;
	for (int i = 0; i <= 30; i++) {
		int now = dist[h - 1][w - 1][i];
		if (now == -1) continue;
	//	cout << now << '\n';
		if (ans == -1 || ans > now) ans = now;
	}
	cout << ans << '\n';
	return 0;
}

bupjae 4년 전 0

dx 및 dy 의 원소 하나가 잘못 들어가있는 것 같습니다.

axa1239 4년 전 0

하.... 긴 시간 헤매던게 이렇게 어이 없는 실수 때문이라니... 절대로 실수 하지 않을 것 같던곳에서 이렇게 틀리게 되네요 ㅠ

정말 감사드립니다!!

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