#include <bits/stdc++.h>
using namespace std;
template<typename t> void umax(t &a, t b) {a = max(a, b);}
template<typename t> void umin(t &a, t b) {a = min(a, b);}
auto steps = initializer_list< pair<int, int> > {
{+1, +0},
{+0, +1},
{-1, -0},
{-0, -1}
};
#define ft first
#define sd second
const int N = 1024;
struct cont;
cont* follow_pipe(int, int);
void extend(cont*, int, int);
int n, m;
string a[N];
bool valid(int i, int j) {
return i >= 0 && j >= 0 && i < n && j < m;
}
bool dig(int i, int j) {
if(!valid(i, j)) return false;
return a[i][j] >= '0' && a[i][j] <= '9';
}
bool pipe(int i, int j) {
if(!valid(i, j)) return false;
int c = a[i][j];
return c == '|' || c == '-' || c == '+';
}
struct cont {
int lx{n}, ly{m}, rx{-1}, ry{-1};
map<int, cont*> nx;
string name; int nmx, nmy{m};
cont(int i, int j) {
extend(this, i, j);
for(name = ""; nmy < m && dig(nmx, nmy); ++nmy)
name += a[nmx][nmy];
for(int i = rx; i >= lx; --i) {
cont*
c = follow_pipe(i, ly - 2); if(c) nx[-i] = c;
c = follow_pipe(i, ry + 2); if(c) nx[-i] = c;
}
}
void make() {
for(auto i : nx) i.sd->make();
cout << name << '\n';
}
};
bool mk[N][N];
void extend(cont *c, int i, int j) {
if(!valid(i, j) || pipe(i, j) || mk[i][j]) return;
mk[i][j] = true;
umin(c->lx, i);
umax(c->rx, i);
umin(c->ly, j);
umax(c->ry, j);
if(dig(i, j)) {
umin(c->nmy, j);
c->nmx = i;
}
for(auto s : steps)
extend(c, i + s.ft, j + s.sd);
}
cont* follow_pipe(int i, int j) {
if(!pipe(i, j) || mk[i][j]) return 0;
mk[i][j] = true;
for(auto s : steps) {
int x = i + s.ft;
int y = j + s.sd;
if(!pipe(x, y)) continue;
if(a[x][y] != a[i][j] &&
a[x][y] != '+' &&
a[i][j] != '+') continue;
cont* res = follow_pipe(x, y);
if(res) return res;
}
if(i + 2 < n
&& a[i][j] == '|'
&& a[i + 1][j] == '-') return new cont(i + 2, j);
return 0;
}
void solve() {
#ifdef _LOCAL
memset(mk, 0, sizeof mk);
#endif
cin >> n >> m;
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(a[i][j] != '1' || dig(i, j - 1) || dig(i, j + 1)) continue;
(new cont(i, j))->make();
return;
}
}
cout << "wat\n";
}
signed main() {
#ifdef _LOCAL
freopen("in.txt", "r", stdin);
int t; cin >> t;
for(int i = 1; i <= t; ++i) {
cerr << "case #" << i << endl;
solve();
cerr << endl;
}
#else
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
#endif
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
896 KB |
Output is correct |
9 |
Correct |
5 ms |
1536 KB |
Output is correct |
10 |
Correct |
13 ms |
3072 KB |
Output is correct |