16924번 십자가 찾기

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

나는 (r, c)에서 dy, dx 배열을 활용해 십자가 모양으로 퍼져 나가는 형식으로 구현했다.

그런데 시간이 56ms나 걸렸다.

다른 분들은 8ms, 4ms 정도 걸린 것 같다.

나중에 시간되면 다시 풀어봐야겠다.

그리고 좀 더 노력하자.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// https://www.acmicpc.net/problem/16924
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
// → ↓ ← ↑
 
int X[4] = { 0, };
int Y[4] = { 0, };
 
int before = 0, N = 0, M = 0;
 
char Map[110][110];
 
bool used[110][110] = { false, };
 
vector<pair<pair<int, int>, int> > v; // {{(행, 열)}, 크기}
 
void draw(int r, int c, int l)
{
    for (int i = 0; i < 4; i++)
    {
        Y[i] = r;
        X[i] = c;        
    }
 
    used[r][c] = true;
 
    while (l--)
    {
        for (int i = 0; i < 4; i++)
        {
            Y[i] += dy[i];
            X[i] += dx[i];
 
            if (!used[Y[i]][X[i]]) used[Y[i]][X[i]] = true;
        }
    }
}
 
void simulation()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (Map[i][j] == '.') continue;
 
            int l = 0, idx = 0; // l은 길이
 
            bool stop = false;
 
            for (int u = 0; u < 4; u++)
            {
                Y[u] = i;
                X[u] = j;
            }
 
            while (1)
            {
                ++l;
 
                for (int d = 0; d < 4; d++)
                {
                    Y[d] += dy[d];
                    X[d] += dx[d];
 
                    if (Y[d] <= 0 || Y[d] > N || X[d] <= 0 || X[d] > M || Map[Y[d]][X[d]] == '.')
                    {
                        stop = true;
                        break;
                    }
                }
 
                if (!stop)
                {
                    draw(i, j, l);
                    v.push_back({ {i, j}, l });
                }
                else break;
            }
        }
    }
}
 
int check()
{
    int ret = 0;
 
    for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) if (used[i][j]) ++ret;
        
    return ret;
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> Map[i][j];
 
            if (Map[i][j] == '*') ++before;
        }
    }
 
    simulation();
 
    if (before != check())
    {
        printf("-1\n");
        return 0;
    }
 
    printf("%d\n", v.size());
 
    for (auto i : v) printf("%d %d %d\n", i.first.first, i.first.second, i.second);
    
    return 0;
}