글 읽기 - 약 80%정도에서 틀리게 나오는데 이유를 모르겠습니다.

chrisjc 7년 전 0

단순 DPS와 메모제이션으로 구현하였는데

질문 게시판에 올려진 테스트 케이스를 다돌려봐도 맞다고 나오는데 뭔가 놓치고 있는건가요?

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
#include <string.h>

using namespace std;

int graph[500][500] = { 0, };
int stepx[4] = { -1, 1, 0, 0 };
int stepy[4] = { 0, 0, -1, 1 };
int cache[500][500];
int visit[500][500] = { 0, };

int count = 0;
int isok(int px, int py,int x,int y);
int n, m;
int DPS(int x, int y);
int main()
{

	

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> graph[j][i];
		}
	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cache[j][i]=-1;

		}
	}

	
	cout << DPS(0, 0) << endl;


	
}

int DPS(int x, int y)
{

	visit[x][y] = 1;

	if (cache[x][y] != -1)
		return cache[x][y];

	int path = 0;

	if ((x == m - 1) && (y == n - 1))
	{
		visit[x][y] = 0;
		return 1;
	}

	int sum = 0;
	path = 0;
	for (int i = 0; i < 4; i++)
	{
		int newx = x + stepx[i];
		int newy = y + stepy[i];
		if (isok(x, y, newx, newy) == 1)
		{
			path = path + DPS(newx, newy);
		}
	}

	cache[x][y] = path;
	visit[x][y] = 0;

	return cache[x][y];


}

int isok(int px, int py, int x, int y)
{

	if (visit[x][y] != 0)
		return 0;

	if (x>m-1 || y>n-1 || y <0 || x< 0)
		return 0;

	if (graph[px][py]<= graph[x][y])
		return 0;

	return 1;
}

chrisjc 7년 전 0

visit 에서 문제가 있었습니다.

isok구문에서 visit[x][y]를 확인하는부분을 지워주니까 정상작동 되었지만

왔던길을 되돌아 갈수는 없지않나요?? 이미 지나오면 그 숫자보다 작게 되어서 역방향으론 못가게 되어있는데

어떻게 저기서 문제가 생길 수 있나요??

chrisjc 7년 전 0

캐쉬를 리턴하는 부분에서 방문 해제를 안했습니다...

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

문제

문제

출처

ICPC

약 80%정도에서 틀리게 나오는데 이유를 모르겠습니다.

chrisjc 7년 전 0

chrisjc 7년 전 0

chrisjc 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말