글 읽기 - (1600)말이 되고픈 원숭이 어디가 틀렸는지 모르겠어요...

shdudtjr77 3년 전 0

체점6%까지 가고 틀리네요...

게시판에 있는 반례들 다 찾아서 해봤는데 제대로 출력 나오는데 자꾸 틀리네요..

어디가 문제가있을 까요??

#include<iostream>
#include<queue>
using namespace std;
int d[4][2] = {1,0,-1,0,0,1,0,-1};
int h[8][2] = { 1,2,2,1,-1,2 - 2,1,2,-1,1,-2,-2,-1,-1,-2 };
int dp[32][204][204];
int map[204][204];

int main() {
	int how;
	int x, y, z, s, u;
	cin >> how;
	cin >> y >> x;
	s = x + 1;
	u = y + 1;
	queue<int> a, b, c;

	//map초기화
	for (int i = 2; i <= s; i++) {
		for (int j = 2; j <= u; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i <= x + 3; i++) {
		map[i][0] = -1;
		map[i][1] = -1;
		map[i][y + 2] = -1;
		map[i][y + 3] = -1;
	}

	for (int i = 0; i <= y + 3; i++) {
		map[0][i] = -1;
		map[1][i] = -1;
		map[x + 2][i] = -1;
		map[x + 3][i] = -1;
	}

	dp[0][2][2] = 1;
	a.push(2); b.push(2); c.push(0);

	bool check = true;
	int j;

	while (!a.empty()) {

		x = a.front(); y = b.front(); z = c.front();
		if (x == s && y == u) {
			break;
		}
		else {
			a.pop(); b.pop(); c.pop();


			for (int i = 0; i < 8; i++) {

				if (map[x + h[i][0]][y + h[i][1]] == 0 && z + 1 <= how) {//말의 형태로 이동하려고 할때 
					check = true;
					j = 0;
					while (check && j <= z + 1) {

						if (dp[j][x + h[i][0]][y + h[i][1]] == 0 || dp[j][x + h[i][0]][y + h[i][1]] > dp[z][x][y] + 1) {
							j++;
						}
						else { check = false; }
					}

					if (check) {
						dp[z + 1][x + h[i][0]][y + h[i][1]] = dp[z][x][y] + 1;
						a.push(x + h[i][0]); b.push(y + h[i][1]); c.push(z + 1);
					}
				}
			}

			for (int i = 0; i < 4; i++) {

				if (map[x + d[i][0]][y + d[i][1]] == 0) {
					j = 0;
					check = true;
					while (check && j <= z) {
						if (dp[j][x + d[i][0]][y + d[i][1]] == 0 || dp[j][x + d[i][0]][y + d[i][1]] > dp[z][x][y] + 1) {
							
							if (j == z) {
								dp[z][x + d[i][0]][y + d[i][1]] = dp[z][x][y] + 1;
								a.push(x + d[i][0]);
								b.push(y + d[i][1]);
								c.push(z);
							}

							j++;
						}
						else { check = false; }
					}


				}
			}
		}
	}
	int min = 999999999;
	check = false;
	for (int i = 0; i <= how; i++) {
		if (min > dp[i][s][u] && dp[i][s][u] != 0&&map[s][u]!=1) {
			min = dp[i][s][u];
			check = true;
		}
	}
	if (!check) { cout << -1; }
	else { cout << min - 1; }
}

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

문제

문제

출처

ICPC

(1600)말이 되고픈 원숭이 어디가 틀렸는지 모르겠어요...

shdudtjr77 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말