글 읽기 - 37퍼에서 막힙니다... 도와주세요

sdsd 1년 전 0

계속 37퍼센트에서 막힙니다.

문제의 예시와 질문게시판의 여러 테스트케이스, 검색해서 찾아낸 테스트케이스 모두 맞다고 나오는데...

어디가 문제인지 잘 모르겠습니다.

고수님들 도움 부탁드립니다..

#include <iostream>
#include <deque>
#include <tuple>
using namespace std;

int map[200][200];
int chk[200][200][31];

//상하좌우
int dc[4] = { 1,0,-1,0 };
int dr[4] = { 0,1,0,-1 };

//말처럼 이동
int horse_dc[8] = { 1,-1,1,-1,2,2,-2,-2 };
int horse_dr[8] = { 2,2,-2,-2,1,-1,1,-1 };
deque<tuple<int, int, int>> visited;

int main() {
	int K, W, H;
	cin >> K;
	cin >> W >> H;

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> map[i][j];
		}
	}


	int now_c, now_r, next_c, next_r, cnt;
	visited.push_back({ 0,0,0 });
    
    //방문여부 체크 및 이동횟수 저장용 배열
    //따라서 시작점 방문을 체크하기 위해 1로 저장.
	chk[0][0][0] = chk[0][0][1] = 1;
	while (!visited.empty()) {
		int size = visited.size();
		for (int i = 0; i < size; i++) {
			now_c = get<0>(visited[0]);
			now_r = get<1>(visited[0]);
            //말처럼 몇 번 움직였는가
			cnt = get<2>(visited[0]);
			visited.pop_front();

            //도착점 도달 시 종료
			if (now_c == H - 1 && now_r == W - 1) break;

			for (int j = 0; j < 4; j++) {
				next_c = now_c + dc[j];
				next_r = now_r + dr[j];
                //범위 안에 들어오고, 장애물 없다면
				if (0 <= next_c && next_c < H && 0 <= next_r && next_r < W && map[next_c][next_r] != 1) {
					//방문하지 않은 지점이라면
                    if (chk[next_c][next_r][cnt] == 0) {
						chk[next_c][next_r][cnt] = chk[now_c][now_r][cnt] + 1;
						//cout << next_c << next_r << cnt << endl;
                        //상하좌우 이동이니까 cnt 그대로
						visited.push_back({ next_c,next_r,cnt });
					}
				}
			}

			for (int j = 0; j < 8; j++) {
				next_c = now_c + horse_dc[j];
				next_r = now_r + horse_dr[j];
                //범위 안에 들어오고, 장애물 없고, 말처럼 이동 가능 횟수가 남으면
				if (0 <= next_c && next_c < H && 0 <= next_r && next_r < W && map[next_c][next_r] != 1 && cnt < K) {
					//방문하지 않은 지점이면
                    if (chk[next_c][next_r][cnt + 1] == 0) {
						chk[next_c][next_r][cnt + 1] = chk[now_c][now_r][cnt] + 1;
						//cout << next_c << next_r << cnt << endl;
                        //말처럼 이동이니까 cnt+1 
						visited.push_back({ next_c,next_r,cnt + 1 });
					}
				}
			}
		}

	}

	int ans = 10000;
	bool a = false;
	for (int i = 0; i <= K; i++) {
		if (chk[H - 1][W - 1][i] != 0) {
            //ans가 초기값 10000 되는것을 방지
			a = true;
			ans = min(ans, chk[H - 1][W - 1][i]);
		}
	}
	if (ans > 0 && a == true) cout << ans - 1 << endl;
	else cout << -1 << endl;

}

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

문제

문제

출처

ICPC

37퍼에서 막힙니다... 도와주세요

sdsd 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말