글 읽기 - 19개 모양 다 해봤는데 반례가 뭘까요?

sjbos66 1년 전 0

凸 모양은 따로 처리하고 다른 것들은 재귀로 처리하고 게시판에 있는 19개 모양 전부 잘 나오는데 틀렸다고 뜨네요...

어디가 틀렸을까요...

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

int n, m;
int p[500][500], t[4][3][2] = {
                     {{-1, -1}, {0, -1}, {1, -1}},
                     {{-1, -1}, {-1, 0}, {-1, 1}},
                     {{-1, 1}, {0, 1}, {1, 1}},
                     {{1, -1}, {1, 0}, {1, 1}}};

int tetromino(int r, int c, int p_r, int p_c, int init, int d)
{
    int max = 0;
    init += p[r][c];

    if (d == 3)
        return init;

    if (r + 1 < n && r + 1 != p_r)
        max = std::max(max, tetromino(r + 1, c, r, c, init, d + 1));
    if (c + 1 < m && c + 1 != p_c)
        max = std::max(max, tetromino(r, c + 1, r, c, init, d + 1));
    if (r - 1 >= 0 && r - 1 != p_r)
        max = std::max(max, tetromino(r - 1, c, r, c, init, d + 1));
    if (c - 1 >= 0 && c - 1 != p_c)
        max = std::max(max, tetromino(r, c - 1, r, c, init, d + 1));

    return max;
}

int main()
{
    int ret;

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> p[i][j];
    }

    int max = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ret = tetromino(i, j, -1, -1, 0, 0);
            if (ret > max)
                max = ret;

            // t tetromino
            for (int k = 0; k < 4; k++)
            {
                if (i + t[k][0][0] >= 0 && i + t[k][0][1] < n && j + t[k][2][0] >= 0 && j + t[k][2][1] < m)
                {
                    ret = p[i][j];
                    for (int l = 0; l < 3; l++)
                    {
                        ret += p[i + t[k][l][0]][j + t[k][l][1]];
                    }

                    if (ret > max)
                        max = ret;
                }
            }
        }
    }

    cout << max;
}

siyamaki 1년 전 1

55번째줄에 t[k][1][0] t[k][1][1]도 경계값 비교를 해야하지 않나요?

t[k][1] 좌표를 계산하지 않은 건 T 모양을 만드는 방법이 기준점을 중심으로 상하좌우에 길이 3인 직선 블록을 위치시키는데 양쪽 끝만 확인하면 가운데는 확인을 안해도 돼서 그렇구요 오랜만에 다시 보니까 55번째 줄에서 t[][][0]이 x좌표고 t[][][1]이 y좌표인데 조건문을 잘못 작성했더라구요 55번째 줄 지적해주셔서 감사합니다 다음처럼 수정해서 통과했습니다

if (i + t[k][0][0] >= 0 && j + t[k][0][1] >= 0 && i + t[k][2][0] < n && j + t[k][2][1] < m)

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

문제

문제

출처

ICPC

19개 모양 다 해봤는데 반례가 뭘까요?

sjbos66 1년 전 0

siyamaki 1년 전 1

sjbos66 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말