글 읽기 - 어디서 틀렸는지를 모르겠습니다.

sejungpk 5년 전 0

범위가 -100000 ~ 100000이라서 map으로 표현했습니다. 생각해보니 T가 200초라 [401][401] 배열로 해도 되지만 map으로 구현했습니다.
~~집에 가면 나올 일이 없기 때문에 방문처리를 해주면서 갔습니다.~~ 방문처리를 하면 안되겟더군요 이길이 아니면 되돌아갈 수 있다라는 조건이 있었습니다.
대게 -1로 초기화를 한 후 검사를 하지만 map으로 구현해서 map에 0이상의 값이 있는 경우 리턴을 해줬습니다. 방식은 다른게 없다고 생각합니다.
예제 인풋 2개는 다 출력됩니다.

#include<iostream>
#include<vector>
#include<string.h>
#include<map>
#include<set>
using namespace std;

map<pair<int, int>, bool > visit;
map<pair<int, int>, int > dp;
int startX, startY;
int endX, endY;
int T;
int N;
set<pair<int, int>> obstacle;
int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
bool isRange(int y, int x)
{
	if (y >= -100000 && x >= -100000 && y <= 100000 && x <= 100000)
		return true;

	return false;
}

int Dfs(int time, pair<int, int>& pos)
{
	if (pos.first == endY && pos.second == endX && time <= T)
		return 1;

	if (time > T)
		return 0;

	if (dp.count(pos) == 1)
		return dp[pos];

	visit[pos] = true;
	dp[pos] = 0;

	for (int i = 0; i < 4; i++)
	{
		int ny = pos.first + dir[i][0];
		int nx = pos.second + dir[i][1];
		pair<int, int> tmp = make_pair(ny, nx);
		if (obstacle.count(tmp) == 0 && isRange(ny, nx)) //장애물이 아니면 어디든 갈 수 있음
		{
			if (!visit[tmp])
			{
				dp[pos] = (dp[pos] + Dfs(time + 1, tmp)) % 1000000007;
			}
		}
	}

	visit[pos] = false;

	return dp[pos] % 1000000007;
}


int main(void)
{
	cin >> startX >> startY;
	cin >> T;
	cin >> endX >> endY;
	cin >> N;
	for (int n = 0; n < N; n++)
	{
		int oX, oY;
		cin >> oX >> oY;
		obstacle.insert(make_pair(oY, oX));
		visit[{oY, oX}] = true;
	}

	pair<int, int> p = { startY, startX };
	int ans = Dfs(0, p);
	cout << ans % 1000000007 << endl;

	return 0;

}

sejungpk 5년 전 0

해결했습니다. 시간 좌표 3차원 배열로 해서 풀었습니다.

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

문제

문제

출처

ICPC

어디서 틀렸는지를 모르겠습니다.

sejungpk 5년 전 0

sejungpk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말