글 읽기 - bfs 문제 질문 있습니다(1600:말이 되고픈 원숭이).. 도와주세요 ㅠㅠ

yunsubaek 7년 전 0

말처럼 이동할 수 있는 횟수와 가로 세로값을 받고 시작위치에서 도착위치까지 bfs로 탐색했습니다.

질문검색에 나온 테스트케이스는 전부 통과하는데 9퍼에서 걸립니다.. 어떤 예외가 있을까요? 고수분들의 도움 부탁드립니다ㅠㅠ

#include<iostream>
#include<queue>
using namespace std;

const int size_ = 202;
const int inf_	= 987654321;
int hcnt;
int r, c;
int result = inf_;
int sx, sy;
int fx, fy;
int dx[12] = { 0,0, 1,-1,-2,-1,1,2, 2, 1,-1,-2 };
int dy[12] = { 1,-1,0, 0, 1, 2,2,1,-1,-2,-2,-1 };
int arr[size_][size_];
//0:monkey,1:horse
int visit[size_][size_][2];

struct pos
{
	int x, y, cnt, hc;
};

int main()
{
    //init
	scanf("%d%d%d", &hcnt, &c, &r);
	sx = 1, sy = 1;
	fx = r, fy = c;
	for (int i = 1; i <= r; ++i)
		for (int j = 1; j <= c; ++j)
		{
			scanf("%d", &arr[i][j]);
			for (int k = 0; k < 2; ++k)
				visit[i][j][k] = inf_;
		}
    //bfs
	queue<pos> q;
	q.push({ sx,sy,0,hcnt });
	visit[sx][sy][0] = 0;
	while (!q.empty())
	{
		pos now = q.front();
		q.pop();
		if (now.x == fx && now.y == fy)
		{
			if (result > now.cnt)result = now.cnt;
		}
		//monkey
		for (int i = 0; i < 4; ++i)
		{
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];
			int ncnt = now.cnt + 1;
			int nhcnt = now.hc;
			if (nx<1 || ny<1 || nx>r || ny>c)continue;
			if (arr[nx][ny] == 1)continue;
			if (visit[nx][ny][0] <= ncnt)continue;
			visit[nx][ny][0] = ncnt;
			q.push({ nx,ny,ncnt,nhcnt });
		}
		if (now.hc > 0)
		{
			//horse
			for (int i = 4; i < 12; ++i)
			{
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				int ncnt = now.cnt + 1;
				int nhcnt = now.hc - 1;
				if (nx<1 || ny<1 || nx>r || ny>c)continue;
				if (arr[nx][ny] == 1)continue;
				if (visit[nx][ny][1] <= ncnt)continue;
				visit[nx][ny][1] = ncnt;
				q.push({ nx,ny,ncnt,nhcnt });
			}
		}
	}
    //output
	printf("%d\n", result == inf_ ? -1 : result);
	return 0;
}

yunsubaek 7년 전 0

visit부분에서 원숭이, 말 방문 2가지로 체크하지 않고 말처럼 이동한 횟수를 메모이제이션 해서 해결했습니다!

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

문제

문제

출처

ICPC

bfs 문제 질문 있습니다(1600:말이 되고픈 원숭이).. 도와주세요 ㅠㅠ

yunsubaek 7년 전 0

yunsubaek 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말