글 읽기 - 1%에서 틀렸습니다. 원인을 혼자찾기 힘들어서 질문합니다!! 도와주세요.

horange89 6년 전 0

우선, ㅓ ㅏ ㅗ ㅜ 의 경우는 배열로 SOLVE 메소드를 통해서 따로 검사했구요.

나머지 모형은 DFS를 이용해서 검사하였습니다.

현재 위치에서 가장 큰 값을 result 배열에 넣어 가장 큰 값을 출력하는 방식을 사용했습니다.

범위 문제인지, 로직에서의 문제인지 모르겠어서 이렇게 질문을 올립니다.

/*
	14500번 테트로미노 : https://www.acmicpc.net/problem/14500 
	 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
*/

#include <cstdio>

int N, M, MAX;
int tMap[503][503];
int result[503][503];
int visit[4][4];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int sx[4][3] = { {0,1,-1},
				{0,0,1},
				{0,0,-1},
				{0,1,-1} };
int sy[4][3] = { {1,0,0},
				{-1,1,0},
				{-1,1,0},
				{-1,0,0} };


void DFS(int n, int m, int cnt, int total)
{

	if(cnt != 4)
	{
		for (int i = 0; i < 4; i++)
		{
			int tmpN = n + dy[i];
			int tmpM = m + dx[i];

			if (0 < tmpN && 0 < tmpM && tmpN <= N && tmpM <= M && visit[tmpN][tmpM] == 0)
			{
				visit[tmpN][tmpM] = 1;
				//printf("cnt = %d total = %d, total+tMap[%d][%d] = %d\n", cnt, total, tmpN, tmpM, total + tMap[tmpN][tmpM]);
				DFS(tmpN, tmpM, cnt + 1, total+tMap[tmpN][tmpM]);
				visit[tmpN][tmpM] = 0;
			}
		}
	}

	else
	{
		//printf("cnt = %d, MAX = %d, total = %d\n", cnt, MAX, total);
		if (MAX < total)
			MAX = total;
	}
}

void SOLVE(int n, int m)
{
	int tmpMax = 0;

	for (int i = 0; i < 4; i++)
	{
		int cnt = 0;
		tmpMax = 0;

		for (int j = 0; j < 3; j++)
		{
			int tmpN = n + sy[i][j];
			int tmpM = m + sx[i][j];

			if (0 < tmpN && 0 < tmpM && tmpN <= N && tmpM <= M)
			{
				cnt++;
				tmpMax += tMap[tmpN][tmpM];

				if (cnt == 3)
				{
					tmpMax += tMap[n][m];
					if (tmpMax > MAX)
						MAX = tmpMax;
				}
			}
		}

	}
}

int main(void)
{
	MAX = -1;

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			scanf("%d", &tMap[i][j]);
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			//printf("i = %d, j = %d\n", i, j);
			visit[i][j] = 1;
			DFS(i,j,1, tMap[i][j]);

			for (int i = 1; i <= N; i++)
			{
				for (int j = 1; j <= M; j++)
				{
					visit[i][j] = 0;
				}
			}

			SOLVE(i, j);
			//printf("MAX = %d\n", MAX);
			result[i][j] = MAX;
			MAX = -1;
		}
	}
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (MAX < result[i][j])
				MAX = result[i][j];
		}
	}
	
	printf("%d\n", MAX);

	return 0;
}

kdk8361 6년 전 0

11, 107~113번 줄이 잘못된 것 같습니다. 그리고 107~113번 줄은

visit[i][j] = 0; 한줄이면 해결되지 않을까요?

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

문제

문제

출처

ICPC

1%에서 틀렸습니다. 원인을 혼자찾기 힘들어서 질문합니다!! 도와주세요.

horange89 6년 전 0

kdk8361 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말