글 읽기 - 반례 찾아주실분 ㅠ

dmzld 4년 전 0

20%쯤에서 실패뜨네요..

기본적으로 dfs로 구하고

ㅏ 모양은 따로 값 구하는 방식입니다.

그리고 이렇게하면 중복이 많은데 없앨 방법이 있을까요?

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int N, M;
//vector<vector<int>> P; // paper
// vector<vector<bool>> C;
int P[500][500];
bool C[500][500];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int res = -1;

void solution(int y, int x, int cnt, int sum){ // dfs for normal shape
	if (cnt == 4){
		if (res < sum)
			res = sum;
		return;
	}

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

		if (cx < 0 || cx >= M || cy < 0 || cy >= N)
			continue;
		if (C[cy][cx])
			continue;
		
		C[cy][cx] = true;
		solution(cy, cx, cnt + 1, sum + P[cy][cx]);
		C[cy][cx] = false;
	}
}

void extra_solution(int y, int x){ // for extra shape
	if (x - 1 >= 0 && y - 1 >= 0 && x + 1 < M){ // ㅗ
		int sum = P[y][x] + P[y][x - 1] + P[y - 1][x] + P[y][x + 1];
		if (res < sum) res = sum;
	}
	if (y + 1 < N && y - 1 >= 0 && x + 1 < M){ // ㅏ
		int sum = P[y][x] + P[y + 1][x] + P[y - 1][x] + P[y][x + 1];
		if (res < sum) res = sum;
	}
	if (x - 1 >= 0 && y + 1 > N && x + 1 < M){ // ㅜ
		int sum = P[y][x] + P[y][x - 1] + P[y + 1][x] + P[y][x + 1];
		if (res < sum) res = sum;
	}
	if (x - 1 >= 0 && y - 1 >= 0 && y + 1 < N){ // ㅓ
		int sum = P[y][x] + P[y][x - 1] + P[y - 1][x] + P[y + 1][x];
		if (res < sum) res = sum;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++){ // y
		for (int j = 0; j < M; j++){ // x
			cin >> P[i][j];
		}
	}

	for (int i = 0; i < N; i++){ // for different start point
		for (int j = 0; j < M; j++){
			memset(C, false, sizeof(C));
			C[i][j] = true;
			solution(i, j, 1, P[i][j]);
			extra_solution(i, j);
			C[i][j] = false;
		}
	}

	cout << res;

	return 0;
}

openingsound 4년 전 1

5 5

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
10 10 10 1 1
1 10 1 1 1

정답은 40

넣으니까 안되네요 저는 dfs중복이 이전에 들렀던거를 다시 들러서 prey, prex를 넘겨줘서 cy가 prey와 같고 cx가 prex와 같다면 실행하지 않는걸 if문에 넣었었습니다.

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

문제

문제

출처

ICPC

반례 찾아주실분 ㅠ

dmzld 4년 전 0

openingsound 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말