글 읽기 - 틀렸습니다 반례

dbswjd0634 5년 전 0

다른 케이스가 있는지 궁금합니다

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<math.h>

using namespace std;
long long int arr[500][500];
long long int dp[500][500] = { 0 };
int n, m;
void change(int a, int b) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (i == a && j == b) return;

			if (i == 0 && j == 0) continue;
			dp[i][j] = 0;
			if (arr[i][j] < arr[i - 1][j]) dp[i][j] += dp[i - 1][j];
			if (arr[i][j] < arr[i + 1][j]) dp[i][j] += dp[i + 1][j];
			if (arr[i][j] < arr[i][j - 1]) dp[i][j] += dp[i][j - 1];
			if (arr[i][j] < arr[i][j + 1]) dp[i][j] += dp[i][j + 1];
		}
}
int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) cin >> arr[i][j];
	dp[0][0] = 1;
	
	int t = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == 0 && j == 0) continue;
			if (arr[i - 1][j] > arr[i][j]) {
				dp[i][j] += dp[i - 1][j];
			}
			if (arr[i + 1][j] > arr[i][j]) {
				dp[i][j] = dp[i][j] + dp[i + 1][j];
			}
			if (arr[i][j - 1] > arr[i][j]) {
				dp[i][j] = dp[i][j] + dp[i][j - 1];
			}
			if (arr[i][j + 1] > arr[i][j]) {
				dp[i][j] = dp[i][j + 1] + dp[i][j];
			}
			if ((arr[i][j] > arr[i - 1][j] || arr[i][j] > arr[i][j - 1]) && dp[i][j] >= 1) {
				if (arr[i][j] > arr[i - 1][j])dp[i - 1][j] += dp[i][j];
				if (arr[i][j] > arr[i][j - 1])dp[i][j - 1] += dp[i][j];
				change(i, j);
			}

		}
	}
	cout << dp[n - 1][m - 1];
	return 0;
}

tony9402 5년 전 0

4 4
16 9 8 1
15 10 7 2
14 11 6 3
13 12 5 4

이게 반례네요

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

문제

문제

출처

ICPC

틀렸습니다 반례

dbswjd0634 5년 전 0

tony9402 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말