글 읽기 - 반례를 간곡히 부탁드리옵니다.

paldad 3년 전 0

안녕하세요.

여러가지 테스트 샘플도 만들어보고 열심히 짱구도 굴려 보았지만 지쳐 버렸습니다..

도움을 부탁드립니다.

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef tuple<int, int, int> t3i;

/**
 * mat 에서 [r][c] 를 중심으로 한
 * size s 크기의 십자가를 놓을수 있는지 확인한다.
 */
bool check(vector<vector<bool> > &mat, int r, int c, int s, int N, int M)
{
    /* 범위 밖 */
    if (r - s < 0 || c - s < 0 || r + s >= N || c + s >= M)
        return false;

    /* 해당 영역에 별이 없음 */
    if (mat[r-s][c] == false ||
        mat[r+s][c] == false ||
        mat[r][c-s] == false ||
        mat[r][c+s] == false)
        return false;

    /* 그 외 경우는 놓을 수 있음 */
    return true;
}

int main(void)
{
    int N, M;

    ios::sync_with_stdio(false);
    cout.tie(0);

    cin >> N >> M;

    /* N-by-M boolean vector create and initialze to false */
    vector<vector<bool> > mat1(N, vector<bool>(M, false));
    vector<vector<bool> > mat2(N, vector<bool>(M, false));

    for (int n = 0; n < N; n++)
    {
        string str;
        cin >> str;

        for (int m = 0; m < M; m++)
        {
            if (str[m] == '.')
                mat1[n][m] = false;
            else
                mat1[n][m] = true;
        }
    }

    vector<t3i> ans;

    /**
     * mat1 과 mat2 를 비교하면서
     * mat2[m][n] 을 중심으로 한 십자가를 놓을수 있는지 확인한다.
     * 최대한 큰 십자가를 놓으려 시도한다.
     */
    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            int sizeok = 0;

            /* 크기를 하나씩 증가시켜 가며 확인한다. */
            for (int s = 1; ;s++)
            {
                if (check(mat1, n, m, s, N, M))
                {
                    /* s == 1 인 경우 중앙에도 표시해야 한다. */
                    if (s == 1)
                        mat2[n][m] = true;

                    mat2[n-s][m] = true;
                    mat2[n+s][m] = true;
                    mat2[n][m-s] = true;
                    mat2[n][m+s] = true;

                    sizeok = s;
                }
                /* s 크기의 십자가를 놓을수 없으면 루프를 탈출한다. */
                else
                {
                    break;
                }
            }

            /**
             * 십자가를 놓은 경우 놓을수 있는 가장 큰 크기의 십자가 위치를 저장한다.
             * 답은 index 를 1부터 하여 출력해야 한다.
             */
            if (sizeok != 0)
                ans.push_back(make_tuple(n+1, m+1, sizeok));
        }
    }

    /* 마지막으로 mat1 와 mat2 가 동일한지 확인한다. */
    for (int n = 0; n < N; n++)
    {
        for (int m = 0; m < M; m++)
        {
            if (mat1[n][m] != mat2[n][m])
            {
                cout << "-1\n";
                return 0;
            }
        }
    }

    /* 십자가를 하나도 놓지 못했거나 M*N 개 이상을 놓은 경우 */
    if (ans.size() == 0 || ans.size() > N*M)
    {
        cout << "-1\n";
        return 0;
    }

    cout << ans.size() << "\n";

    for (auto t: ans)
    {
        int x, y, s;
        tie(x, y, s) = t;
        cout << x << " " << y << " " << s << "\n";
    }

    return 0;
}

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

문제

문제

출처

ICPC

반례를 간곡히 부탁드리옵니다.

paldad 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말