#include "bits/stdc++.h"
using namespace std;
int n, m;
char s[1111][1111];
bool vis[1111][1111];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int a[1111][1111];
int id[1111][1111];
bool inside(int x, int y) {
if(0 <= x && x < n) {
if(0 <= y && y < m) {
return true;
}
}
return false;
}
bool outline(int i, int j) {
return (s[i][j] == '-' || s[i][j] == '|' || s[i][j] == '+');
}
int val;
int get(int x, int y) {
while(y > 0 && isdigit(s[x][y-1])) {
--y;
}
int ans = 0;
while(y < m && isdigit(s[x][y])) {
ans = 10 * ans + (s[x][y] - '0');
++y;
}
return ans;
}
void fill(int x, int y) {
vis[x][y] = true;
if(isdigit(s[x][y])) {
val = get(x, y);
}
for(int i = 0; i < 4; i++) {
int p = x + dx[i];
int q = y + dy[i];
if(inside(p, q) && vis[p][q] == false && (s[p][q] == '.' || isdigit(s[p][q]))) {
fill(p, q);
}
}
}
void mark(int x, int y) {
a[x][y] = val;
for(int i = 0; i < 4; i++) {
int p = x + dx[i];
int q = y + dy[i];
if(inside(p, q) && a[p][q] == 0 && (s[p][q] == '.' || isdigit(s[p][q]))) {
mark(p, q);
}
}
}
int container(int x, int y) {
for(int i = 0; i < 4; i++) {
int p = x + dx[i];
int q = y + dy[i];
if(inside(p, q) && id[p][q] > 0) return id[p][q];
}
return 0;
}
int root;
int child;
void finder(int x, int y) {
// cout << x << "--" << y << endl;
vis[x][y] = true;
int ad = container(x, y);
if(ad > 0 && ad != root) {
child = ad;
return ;
}
for(int i = 0; i < 4; i++) {
int p = x + dx[i];
int q = y + dy[i];
if(inside(p, q) && vis[p][q] == false && outline(p, q) && id[p][q] == 0) {
finder(p, q);
}
}
}
typedef pair <int, int> pii;
vector <pii> g[1000010];
void trav(int x) {
sort(g[x].begin(), g[x].end());
reverse(g[x].begin(), g[x].end());
for(auto i : g[x]) {
trav(i.second);
}
printf("%d\n", x);
}
int main(int argc, char const *argv[])
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) {
scanf("%s", s[i]);
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(vis[i][j] == false) {
if(isdigit(s[i][j]) || s[i][j] == '.') {
val = -1;
fill(i, j);
if(val != -1) {
mark(i, j);
}
}
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
id[i][j] = a[i][j];
if(outline(i, j)) {
for(int x = -1; x <= 1; x++) {
for(int y = -1; y <= 1; y++) {
int p = i + x;
int q = j + y;
if(inside(p, q) && a[p][q] > 0) {
id[i][j] = a[p][q];
}
}
}
}
}
}
/*
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cout << id[i][j] << " ";
}
cout << endl;
}
*/
memset(vis, false, sizeof vis);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(id[i][j] == 0 && vis[i][j] == false && s[i][j] == '-' && container(i, j)) {
root = container(i, j);
finder(i, j);
g[root].push_back(pii(i, child));
// cout << root << " " << child << endl;
}
}
}
trav(1);
return 0;
}
Compilation message
clickbait.cpp: In function 'int main(int, const char**)':
clickbait.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
clickbait.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
25976 KB |
Output is correct |
| 2 |
Correct |
24 ms |
25976 KB |
Output is correct |
| 3 |
Correct |
24 ms |
25976 KB |
Output is correct |
| 4 |
Correct |
23 ms |
25976 KB |
Output is correct |
| 5 |
Correct |
23 ms |
26016 KB |
Output is correct |
| 6 |
Correct |
23 ms |
26016 KB |
Output is correct |
| 7 |
Correct |
23 ms |
26072 KB |
Output is correct |
| 8 |
Correct |
28 ms |
29120 KB |
Output is correct |
| 9 |
Correct |
28 ms |
31236 KB |
Output is correct |
| 10 |
Correct |
97 ms |
39124 KB |
Output is correct |
