글 읽기 - 어디가 틀렸을까요?

dolmul5000 3년 전 0

답보고 비슷하게 푼 것 같은데, 어느 부분에서 잘못 생각했는지 모르겠습니다.

#include <iostream>
#include <algorithm>
using namespace std;
#pragma warning(disable: 4996)

int arr[500][500];
int visited[500][500];
int N, M;
int Max = -1;

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

void DFS(int x, int y, int sum, int cnt)
{
	

	if (cnt == 3)
	{
		Max = max(Max, sum);
		return;
	}

	for (int i = 0; i < 4; ++i)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || ny < 0 || nx >= M || ny >= N)
			continue;
		else if (visited[nx][ny])
			continue;

		visited[x][y] = true;
		DFS(nx, ny, sum + arr[nx][ny], cnt + 1);
		visited[nx][ny] = false;
	}

}

void exeption(int row, int col)
{
	// x, y에 해당하는 위치에서 n과 m을 보고 인덱스의 범위를 넘어가지 않는지 판단한다.
	// 이것이 가능한 경우에 sum을 구해서 max값을 확인해본다. row < N && col < M

	// ㅏㅓ 왼쪽상단을 기준
	if (row + 2 < N && col + 1 < M)
	{
		Max = max(Max, arr[row][col] + arr[row + 1][col] + arr[row + 2][col] + arr[row + 1][col + 1]);
		Max = max(Max, arr[row + 1][col] + arr[row][col + 1] + arr[row + 1][col + 1] + arr[row + 2][col + 1]);
	}

	// ㅗ ㅜ
	if (row + 1 < N && col + 2 < M)
	{
		Max = max(Max, arr[row][col + 1] + arr[row + 1][col] + arr[row + 1][col + 1] + arr[row + 1][col + 2]);
		Max = max(Max, arr[row][col] + arr[row][col + 1] + arr[row][col + 2] + arr[row + 1][col + 1]);
	}

}

void Input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			scanf("%d", &arr[i][j]);
		}
	}
}
int main()
{
	// ㅜ 모양을 제외하고는, 모든 정점에 대해서 DFS를 돌리면 
	// 결국 우리가 원하는 회전, 대칭된 모든 경우를 찾게 된다.
	// 이 정점을 방문한 경우의 처리와 그렇지 않은 경우의 처리(백트래킹)
	// 어느 위치로 뻗어가든지, 결국에는 도형들의 회전/대칭의 경우에 속한다.
	// 모든 위치에 대해서 DFS를 해주면서, 백트래킹, ㅗ ㅓ ㅏ ㅗ 의 경우에는 예외처리
	// 좌우상하로 움직이는 경우로는 나올 수 없는 모양이다.

	Input();
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			memset(visited, 0, sizeof(visited));
			DFS(i, j, arr[i][j], 0);
			exeption(i, j);
		}
	}
	cout << Max << endl;

	system("pause");
	return 0;
}

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

문제

문제

출처

ICPC

어디가 틀렸을까요?

dolmul5000 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말