[20/07/05] D. 십자가 찾기 (16924)

 

어려운 건 없었는데 구현이 너무너무! 힘들었다. 로직은 간단하다. 먼저 십자가를 찾고 배열에서 십자가를 전부 '.'으로 만들고 마지막으로 전부 '.'만 있는지 확인한다. 처음에 그냥 십자가만 찾고 십자가가 하나도 없다면 -1로 출력하려면 했는데 틀렸었다. 비슷한 문제 풀 때 다시 확인했던 게 떠올라서 십자가를 다시 확인해주니 성공했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int x[4] = {0, -1, 0, 1};
int y[4] = {1, 0, -1, 0};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    vector<string> v(n);

    for (int i = 0; i < n; i++)
        cin >> v[i];
    
    vector<ii> ans;
    vector<int> s;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (v[i][j] == '.')
                continue;

            int k = 0;
            int x_p = i;
            int y_p = j;
            
            
            vector<int> count(4, 0);
            while (k != 4)
            {
                x_p += x[k];
                y_p += y[k];
                
                if (x_p < 0 || n <= x_p || y_p < 0 || m <= y_p)
                {
                    k++;
                    x_p = i;
                    y_p = j;
                    continue ;
                }
                if (v[x_p][y_p] == '*')
                    count[k]++;
                else
                {
                    k++;
                    x_p = i;
                    y_p = j;
                }
            }

            
            
            int input = min({count[0], count[1], count[2], count[3]});
            if (input != 0)
            {
                s.push_back(input);
                ans.emplace_back(i, j);
            }
        }
    }
    
    
    for (int i = 0; i < ans.size(); i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int x_p = ans[i].xx;
            int y_p = ans[i].yy;
            v[x_p][y_p] = '.';
            
            for (int k = 0; k < s[i]; k++)
            {
                x_p += x[j];
                y_p += y[j];
                v[x_p][y_p] = '.';
            }
        }
        
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (v[i][j] == '*')
            {
                printf("-1\n");
                return 0;
            }
        }
    }
    
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%d %d %d\n", ans[i].xx + 1, ans[i].yy + 1, s[i]);
    }
    
    return 0;
}