글 읽기 - 고수님들 도와주세요

m48tank1 8년 전 0

DFS로 접근해서 판다가 살수 있는 날을 구했습니다.

* 종료 조건을 찾지 못해서 전부 검색을 하게 되어 time out이 발생합니다. 종료 조건은 어떻게 해야할까요?

가지치기를 해야할거 같은데, 모르겠습니다.ㅜ.ㅜ

* 해당 문제분류가 정렬로 되어 있는데, 정렬로 풀려면 힌트가 어떻게 해야할까요 ?

#if 1
#include <stdio.h>
#define MAP_SIZE	501
int MAP[MAP_SIZE][MAP_SIZE];
int MAP_DAY[MAP_SIZE][MAP_SIZE];
int N;
int K = 0;

int Safe(int x, int y)
{
	if ((x >= 0 && x < N) && (y >= 0 && y < N)) return 1;
	else return 0;
}

int DFS(int x, int y, int day)
{
	int i = 0;
	int dx[4] = { -1, 1, 0, 0 };
	int dy[4] = { 0, 0, -1, 1 };
	//printf("%d %d %d %d \n", x, y, MAP[x][y], day);

	if (day > K) K = day;
	
	for (i = 0; i < 4; i++)
	{
		if (Safe(x + dx[i], y + dy[i]) && MAP[x][y] < MAP[x + dx[i]][y + dy[i]])
		{
			DFS(x + dx[i], y + dy[i], day + 1);
		}
	}

	return 0;
}

int main()
{
	int i, j;
	//freopen("1937.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d\n", &N);

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			scanf("%d ", &MAP[i][j]);
		}
	}

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			//printf("------------------------\n");
			DFS(i, j, 1); 
		}
	}
	

	printf("%d\n", K);
	return 0;

}

#endif

pl0892029 8년 전 0

DP LIS 를 아시면 이쁘게 푸실 수 있습니다.

다익스트라로도 풀 수 있습니다.

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

문제

문제

출처

ICPC

고수님들 도와주세요

m48tank1 8년 전 0

pl0892029 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말