글 읽기 - 14500 테트로미노 문제 질문입니다.

pyd6119 4년 전 2

2, 3번 예제 답은 맞는데 1번 예제의 답이 19가 아닌 21이 자꾸 나오네요.

그 원인이 무엇인지 알 수 있을까요?

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 501
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { 1, -1, 0, 0 };
bool visit[MAX][MAX];
int map[MAX][MAX];
int N, M; // 세로, 가로
int fuckSum = 0; // ㅗ 모양의 합의 최댓값
int maxSum = 0;
void fuck(int y, int x) {
	
	fuckSum = 0;
	// ㅗ 모양 / 현재 좌표는 ㅡ 모양에서 중심
	if (1 <= y && y <= N - 1 && 1 <= x && x < M - 1)
		fuckSum = max(fuckSum, map[y][x] + map[y][x - 1] + map[y][x - 1] + map[y][x + 1]);
	// ㅏ 모양 / 현재 좌표는 ㅣ 모양에서 중심
	if (1 <= y && y < N - 1 && 1 <= x && x <= M - 1)
		fuckSum = max(fuckSum, map[y][x] + map[y][x + 1] + map[y - 1][x] + map[y + 1][x]);
	// ㅜ 모양 
	if (0 <= y && y < N - 1 && 1 <= x && x < M - 1)
		fuckSum = max(fuckSum, map[y][x] + map[y + 1][x] + map[y][x - 1] + map[y][x + 1]);
	// ㅓ 모양
	if (1 <= y && y < N - 1 && 1 <= x && x <= M - 1)
		fuckSum = max(fuckSum, map[y][x] + map[y][x - 1] + map[y - 1][x] + map[y + 1][x]);
	maxSum = max(maxSum, fuckSum);
}
// 4개의 그림에 대한 dfs
void dfs(int y, int x, int cnt, int sum) {
	if (cnt == 4) { // 그림이 완성되면
		maxSum = max(maxSum, sum);
		return;
	}
	
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= ny && ny < N && 0 <= nx && nx < M && !visit[ny][nx]) {
			visit[ny][nx] = true;
			dfs(ny, nx, cnt + 1, sum + map[ny][nx]);
			visit[ny][nx] = false; // 방문 해제. 다음 테트로미노 사용을 위해
		}
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visit[i][j] = true;
			dfs(i, j, 1, map[i][j]); // 4개의 그림에 대한 dfs 시작
			fuck(i, j); // ㅗ모양에 대해 시작
			visit[i][j] = false; // 테트로미노 재사용을 위해 방문 설정 해제
		}
	}
	cout << maxSum;
	return 0;
}

pyd6119 4년 전 1

fuck 함수에서 ㅗ 모양에서 map[y][x-1]이 두번 들어가있었네요;

한개를 map[y - 1][x]로 수정해서 완료했습니다.

kscodebase 4년 전 0

함수 명에서 웃고 갑니다 :)

다른 분 코드를 참고하려고 질문을 검색하고 있었는데, 이런 부분에서 즐거움을 느끼고 가네요

whtnwkd 3년 전 0

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

14500 테트로미노 문제 질문입니다.

pyd6119 4년 전 2

pyd6119 4년 전 1

kscodebase 4년 전 0

whtnwkd 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말