글 읽기 - 반례 찾아주시면 감사하겠습니다!

tompark58981 1년 전 0

전에 한번 올렸는데 잘못된 코드를 착각하고 올려서 다시 올리겠습니다...

다시 찾아주시면 정말 감사드리겠습니다!

#include<iostream>
using namespace std;

int board[501][501];
bool check[501][501];
int xd[4] = {1,-1,0,0};
int yd[4] = {0,0,1,-1};
int N,M;

int dfs(int x, int y, int sum, int cnt){

    int best=0;

    if(cnt==3){
        sum += board[y][x];
        return sum;
    }


    for(int i=0;i<4;i++){
        int nx = x+xd[i];
        int ny = y+yd[i];
        if(nx<0||nx>=M||ny<0||ny>=N) continue;
        if(check[ny][nx]) continue;
        check[y][x] = true;
        best = max(best, dfs(nx,ny,sum+board[y][x],cnt+1));
        check[y][x] = false;
    }

    return best;
}

int shape1(int x, int y){
    //O O O
    //  O     
    if(x-1<0||x+1>=M||y+1>=N)
        return -1;

    return board[y][x]+board[y][x-1]+board[y][x+1]+board[y+1][x];
}

int shape2(int x, int y){
    // O
    // O O
    // O
    if(x+1>=M||y+1>=N||y-1<0) return -1;

    return board[y][x]+board[y-1][x]+board[y+1][x]+board[y][x+1];
}

int shape3(int x, int y){
    //   O
    // O O
    //   O

    if(x-1<0||y+1>=N||y-1<0) return -1;
    return board[y][x]+board[y-1][x]+board[y+1][x]+board[x-1][y];
}

int shape4(int x, int y){
    //   0
    // 0 0 0
    
    if(x-1<0||x+1>=M||y-1<0) return -1;

    return board[y][x]+board[y-1][x]+board[y][x-1]+board[y][x+1];
}

int moreShape(int x, int y){
    int best = 0;

    best = max(best, shape1(x,y));
    best = max(best, shape2(x,y));
    best = max(best, shape3(x,y));
    best = max(best, shape4(x,y));

    return best;
};

int main(){

    cin >> N >> M;

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

    int best = 0;

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            best = max(best, dfs(j,i,0,0));
            best = max(best, moreShape(j,i));
        }
    }

    cout << best << '\n';

    return 0;
}

wjdwodud11 1년 전 0

4 4

1 100 1 1

1 8 1 1

10 8 11 1

1 1 1 1

출력: 216

정답: 127

tompark58981 1년 전 0

정말 감사합니다!!

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

문제

문제

출처

ICPC

반례 찾아주시면 감사하겠습니다!

tompark58981 1년 전 0

wjdwodud11 1년 전 0

tompark58981 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말