글 읽기 - 질문란 반례도 다 통과하는데 틀렸다고 나옵니다.

dragonite 6년 전 0

안녕하세요.

주어진 예제와 질문란의 반례는 모두 맞게 나오는데, 틀립니다가 나옵니다.

어디가 틀렸을까요..

/*
16:33
테트로미노 시작

1. ㅗ 모양의 최대합 기능
2. 나머지 모양 최대합 기능.
3. 위 의 두 개 중에 큰 값을 출력
*/

#include <iostream>
#include <algorithm>
using namespace std;

#define SIZE 5 // 505
int map[SIZE][SIZE];
int visit[SIZE][SIZE];
int maxVal;
int N, M;
int x, y;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int minVal = 2123456789;

void problemIn() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
}

void dfs(int depth, int cx, int cy, int sum) {

	if (depth == 4) {
		maxVal = max(maxVal, sum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nx = cx + dx[i];
		int ny = cy + dy[i];
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (visit[nx][ny] == 0) {
			visit[nx][ny] = 1;
			dfs(depth + 1, nx, ny, sum + map[nx][ny]);
			visit[nx][ny] = 0;
		}
	}
	visit[cx][cy] = 0;
}

void star_dfs(int x, int y) {

	if (y + 1 >= M || y - 1 < 0 || x + 1 >= N || x - 1 < 0) return;
	int sum2 = 0;
	minVal = 2123456789;
	sum2 += map[x][y] + map[x][y + 1] + map[x][y - 1] + map[x + 1][y] + map[x - 1][y];
	minVal = min(minVal, map[x][y + 1]);
	minVal = min(minVal, map[x][y - 1]);
	minVal = min(minVal, map[x + 1][y]);
	minVal = min(minVal, map[x - 1][y]);
	sum2 -= minVal;

	maxVal = max(maxVal, sum2);
	return;
}


void solve() {

	// 4가지 모양
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visit[i][j] = 1;
			dfs(1, i, j, map[i][j]);
			visit[i][j] = 0;
		}
	}

	// 별표에서 가장 작은 가장 자리를 하나 뺌.
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			star_dfs(i, j);
		}
	}
}

int main() {
	problemIn();
	solve();
	cout << maxVal << endl;
	return 0;
}

jh05013 6년 전 1

3 3
2 2 2
1 2 1
1 1 1

dragonite 6년 전 1

감사합니다!!!

다른 곳에서 틀린줄 알았는데....

ㅗ 모양에 대해서 찾는 부분에서 틀렸네요

감사합니다!!!

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

문제

문제

출처

ICPC

질문란 반례도 다 통과하는데 틀렸다고 나옵니다.

dragonite 6년 전 0

jh05013 6년 전 1

dragonite 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말