백준 16924 십자가 찾기(c++)

https://www.acmicpc.net/problem/16924

16924번: 십자가 찾기

이 문제는 해당 격자판에서 다음과 같은 십자가를 몇 개 만들 수 있는지 물어보는 문제입니다. 해당 인덱스에서 상하좌우 비교해서 *가 된다면 해당 부분과 크기를 push 해주면 되는 간단한 문제지면 예외의 경우가 존재합니다.

 

예외 케이스

*

***

*

*

 다음과 같은 부분은 제일 아래쪽 *이 크기가 1인 십자가에 속하지 않기에, -1을 출력 해줘야 합니다. 이러한 경우를 방지하기 위해 check변수를 두었고, check변수가 false이고 해당 인덱스 값이 *이면 -1을 출력해주면 끝입니다.

<코드>

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
bool check[100][100];
int main()
{
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<tuple<int, int, int>> ans;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == '*')
            {
                int l = 0;
                for (int k = 1;; k++)
                {
                    if (i + k < n && i - k >= 0 && j + k < m && j - k >= 0)
                    {
                        if (a[i + k][j] == '*' && a[i - k][j] == '*' && a[i][j + k] == '*' && a[i][j - k] == '*')
                        {
                            l = k;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
                if (l > 0)
                {
                    ans.push_back(make_tuple(i + 1, j + 1, l));
                    check[i][j] = true;
                    for (int k = 1; k <= l; k++)
                    {
                        check[i + k][j] = true;
                        check[i - k][j] = true;
                        check[i][j - k] = true;
                        check[i][j + k] = true;
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == '*' && check[i][j] == false)
            {
                cout << -1 << '\n';
                return 0;
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto &t : ans)
    {
        int x, y, len;
        tie(x, y, len) = t;
        cout << x << ' ' << y << ' ' << len << '\n';
    }
    return 0;
}