알고리즘 문제/BOJ
16924번 십자가 찾기
parkit
2019. 3. 18. 20:49
728x90
반응형
https://www.acmicpc.net/problem/16924
나는 (r, c)에서 dy, dx 배열을 활용해 십자가 모양으로 퍼져 나가는 형식으로 구현했다.
그런데 시간이 56ms나 걸렸다.
다른 분들은 8ms, 4ms 정도 걸린 것 같다.
나중에 시간되면 다시 풀어봐야겠다.
그리고 좀 더 노력하자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #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; } | cs |
728x90
반응형