글 읽기 - 어디가 틀렸는지 알려주실 수 있나요?(c++,bfs)

112224 4년 전 0

말의 이동 횟수가 더 클 경우 큐에 넣어주는 방식으로 했더니 메모리 초과가 나오더라구요.

그래서 visit 배열을 i,j 와 말로 이동한 횟수로 잡아주었습니다.

이렇게 하니까 메모리 초과는 나지 않는데 WA가 발생하네요.

로직에 문제점이 잘 보이지 않아서요 ㅠㅠ

반례 제시나 문제점 지적해주시면 감사하겠습니다.

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

int di[4][2] = { 1,0,0,1,-1,0,0,-1 };
int jum[8][2] = { 2,1,2,-1,1,2,1,-2,-2,1,-2,-1,-1,2,-1,1 };
typedef struct ii
{
	int i, j,ans,hor;
}ii;
bool visit[201][201][31];
int graph[201][201];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int k, w, h; cin >> k >> w >> h;

	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			cin >> graph[i][j];

	int ans = -1;
	queue<ii>q; q.push({ 1,1,0,k });
	while (!q.empty())
	{
		ii now = q.front(); q.pop();

		int ii = now.i, jj = now.j, ret = now.ans, hor = now.hor;
		if (ii == h && jj == w)
		{
			ans = ret;
			break;
		}
		if (now.hor > 0)
		{
			for (int i = 0; i < 8; i++)
			{
				int ni = ii + jum[i][0], nj = jj + jum[i][1];
				if (ni >= 1 && ni <= h && nj >= 1 && nj <= w)
				{
					if (!visit[ni][nj][hor - 1]&&graph[ni][nj]==0)
					{
						visit[ni][nj][hor - 1] = true;
						q.push({ ni,nj,ret + 1,hor - 1 });
					}
				}
			}
		}
		for (int i = 0; i < 4; i++)
		{
			int ni = ii + di[i][0], nj = jj + di[i][1];
			if (ni >= 1 && ni <= h && nj >= 1 && nj <= w)
			{ 
				if (graph[ni][nj]==0&&!visit[ni][nj][hor])
				{
					visit[ni][nj][hor] = true;
					q.push({ ni,nj,ret + 1,hor });
				}
			}
		}
	}
	cout << ans << '\n';
	
}

112224 4년 전 0

말 이동 배열 숫자를 잘못 적어놨습니다.

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

문제

문제

출처

ICPC

어디가 틀렸는지 알려주실 수 있나요?(c++,bfs)

112224 4년 전 0

112224 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말