#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1024;
char mp[maxn][maxn];
int n,m,tot,ans[maxn * maxn],id[maxn][maxn],vis[maxn][maxn],deltax[] = {-1,1,0,0},deltay[] = {0,0,-1,1};
inline bool chk(int x,int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
struct point{int x,y;};
inline void bfs(point s,int col){
queue<point> q;
q.push(s);vis[s.x][s.y] = 1;
while(!q.empty()){
point now = q.front();q.pop();
id[now.x][now.y] = col;
for(int i = 0;i < 4;i++){
int nx = now.x + deltax[i],ny = now.y + deltay[i];
if(!chk(nx,ny) || vis[nx][ny])continue;
if(mp[nx][ny] == '.')q.push(point{nx,ny}),vis[nx][ny] = 1;
else id[nx][ny] = col,vis[nx][ny] = 1;
}
}
}
inline int find(point now){
while(!id[now.x][now.y]){
vis[now.x][now.y] = 1;
if(mp[now.x][now.y] == '-'){
if(!vis[now.x][now.y - 1])now.y--;
else if(!vis[now.x][now.y + 1])now.y++;
}else if(mp[now.x][now.y] == '|')now.x++;
else if(mp[now.x][now.y] == '+'){
for(int i = 0;i < 4;i++){
int nx = now.x + deltax[i],ny = now.y + deltay[i];
if(chk(nx,ny) && !vis[nx][ny] && mp[nx][ny] != '.'){
now.x = nx,now.y = ny;
break;
}
}
}
}
return id[now.x][now.y];
}
struct edge{
int v,d;
bool operator < (const edge &rhs)const{
return d > rhs.d;
}
};
vector<edge> G[maxn * maxn];
inline void addedge(int u,int v,int d){
G[u].push_back(edge{v,d});
}
inline void dfs(int u){
for(int i = 0;i < G[u].size();i++){
int v = G[u][i].v;
dfs(v);
}
ans[++tot] = u;
}
int main(){
// freopen("clickbait.in","r",stdin);
// freopen("clickbait.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++)scanf("%s",mp[i] + 1);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(isdigit(mp[i][j])){
int now = 0;
for(int k = j;isdigit(mp[i][k]);j = k,k++)now = now * 10 + mp[i][k] - '0';
bfs(point{i,j},now);
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(mp[i][j] == '|')
if(mp[i][j - 1] == '-')addedge(id[i][j],find(point{i,j - 1}),i);
else if(mp[i][j + 1] == '-')addedge(id[i][j],find(point{i,j + 1}),i);
for(int i = 1;i < maxn;i++)
if(G[i].size() > 1)sort(G[i].begin(),G[i].end());
dfs(1);
for(int i = 1;i <= tot;i++)printf("%d\n",ans[i]);
return 0;
}
Compilation message
clickbait.cpp: In function 'void dfs(int)':
clickbait.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0;i < G[u].size();i++){
| ~~^~~~~~~~~~~~~
clickbait.cpp: In function 'int main()':
clickbait.cpp:78:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
78 | if(mp[i][j] == '|')
| ^
clickbait.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
clickbait.cpp:68:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
68 | for(int i = 1;i <= n;i++)scanf("%s",mp[i] + 1);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1084 ms |
25600 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1090 ms |
25208 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1093 ms |
25472 KB |
Time limit exceeded |
| 4 |
Correct |
17 ms |
25088 KB |
Output is correct |
| 5 |
Correct |
17 ms |
25472 KB |
Output is correct |
| 6 |
Correct |
17 ms |
25472 KB |
Output is correct |
| 7 |
Correct |
17 ms |
25600 KB |
Output is correct |
| 8 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 9 |
Execution timed out |
1090 ms |
29952 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1090 ms |
34552 KB |
Time limit exceeded |
