글 읽기 - 보드 2차원 배열 길이가 왜 301x301 이어야 할까요. 300x300이 아니라

stlee 2년 전 0

I의 최대 값은 300이기 때문에,

300x300의 visit 테이블을 만들었는데요

자꾸 틀리더라고요.

그래서 301x301로 바꾸었더니 통과가 되었습니다.

주어지는 위치도 {0, ... , I-1} x {0, ... , I-1}이라서

300x300으로 잡아도 오류가 안나야 할 것 같은데

이상하네요...

혹시 위치가 I 로 주어지는 경우도 있는걸까요?

#include "bits/stdc++.h"
using namespace std;
int T, I;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

//*****************************************
bool visit[301][301];
// bool visit[300][300]으로 하면 틀렸다고 합니다.
//*****************************************


inline bool is_in_board(int x, int y)
{
	if(x < 0) return false;
	if(x >= I) return false;
	if(y < 0) return false;
	if(y >= I) return false;
	return true;
}
int get_min_moves(int x1, int y1, int x2, int y2)
{
	queue<pair<pair<int, int>, int>> q;
	memset(visit, 0, sizeof(visit));
	q.push(make_pair(make_pair(x1, y1), 0));
	while(!q.empty())
	{
		const pair<int, int> &cur = q.front().first;
		int dist = q.front().second;
		q.pop();
		if(visit[cur.first][cur.second]) continue;
		visit[cur.first][cur.second] = true;
		if(cur.first == x2 && cur.second == y2) return dist;
		for(int i=0;i<8;i++)
		{
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if(is_in_board(nx, ny) && !visit[nx][ny])
			{
				q.push(make_pair(make_pair(nx, ny), dist + 1));
			}
		}
	}
	return -1;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	return 0;
	cin >> T;
	while(T--)
	{
		cin >> I;
		int x1, y1, x2, y2;
		cin >> x1 >> y1;
		cin >> x2 >> y2;
		int min_moves = get_min_moves(x1, y1, x2, y2);
		cout << min_moves << "\n";
	}
	return 0;
}

djm03178 2년 전 0

301로 된 이 코드 그대로 내도 틀립니다.

stlee 2년 전 0

아 이 코드는 Clang(C++17)로 내셔야 합니다...

djm03178 2년 전 0

저도 질문자님의 제출 현황을 보고 C++17 (Clang)으로 냈는데 틀렸습니다. 사실 그건 49번째 줄 때문인데, 왜 그게 들어갔는지는 모르겠지만 질문을 올리실 때에는 제출했던 코드를 그대로 올려주셔야 합니다.

일단 그걸 지워도 300으로 했을 때 틀리는 걸 보긴 했습니다.

djm03178 2년 전 1

전혀 관계 없어보이지만, 놀랍게도 문제는 28번째 줄입니다. 큐에 들어있는 원소를 참조자로 받아올 경우 pop을 하는 순간 변수가 사라지기 때문에 더 이상 사용할 수 없는 상태가 되고, 이 값을 사용하는 것은 undefined behavior가 됩니다. 참조자만 지워주면 300으로 해도 맞습니다.

stlee 2년 전 0

죄송합니다 ㅜㅜ 복사하다가 return 0;이 잘못들어갔네요;

통과된 소스입니다.

#include "bits/stdc++.h"
using namespace std;
int T, I;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool visit[301][301];
inline bool is_in_board(int x, int y)
{
	if(x < 0) return false;
	if(x >= I) return false;
	if(y < 0) return false;
	if(y >= I) return false;
	return true;
}
int get_min_moves(int x1, int y1, int x2, int y2)
{
	queue<pair<pair<int, int>, int>> q;
	memset(visit, 0, sizeof(visit));
	q.push(make_pair(make_pair(x1, y1), 0));
	while(!q.empty())
	{
		const pair<int, int> &cur = q.front().first;
		int dist = q.front().second;
		q.pop();
		if(visit[cur.first][cur.second]) continue;
		visit[cur.first][cur.second] = true;
		if(cur.first == x2 && cur.second == y2) return dist;
		for(int i=0;i<8;i++)
		{
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if(is_in_board(nx, ny) && !visit[nx][ny])
			{
				q.push(make_pair(make_pair(nx, ny), dist + 1));
			}
		}
	}
	return -1;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> T;
	while(T--)
	{
		cin >> I;
		int x1, y1, x2, y2;
		cin >> x1 >> y1;
		cin >> x2 >> y2;
		int min_moves = get_min_moves(x1, y1, x2, y2);
		cout << min_moves << "\n";
	}
	return 0;
}

stlee 2년 전 0

와... 정말 그렇네요

정말 생각지도 못한 부분이었습니다.

이걸 발견하신게 정말 대단한것같네요...

감사합니다!!!!

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

문제

문제

출처

ICPC

보드 2차원 배열 길이가 왜 301x301 이어야 할까요. 300x300이 아니라

stlee 2년 전 0

djm03178 2년 전 0

stlee 2년 전 0

djm03178 2년 전 0

djm03178 2년 전 1

stlee 2년 전 0

stlee 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말