#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3yqVz8E ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
signed main(){
_3yqVz8E;
int h,w;
cin>>h>>w;
vec(vec(char)) a(h,vec(char)(w));
rep(i,h){
rep(j,w){
cin>>a[i][j];
}
}
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
auto ok=[&](int i,int j)->bool{
return i>=0 and j>=0 and i<h and j<w;
};
vec(vi) usd(h,vi(w));
vi lebs;
using Fp=pair<pii,pii>;
map<int,Fp> loc;
rep(i,h){
rep(j,w){
if(usd[i][j]) continue;
if(a[i][j]!='.' and a[i][j]!='+' and a[i][j]!='-' and a[i][j]!='|'){
assert(a[i][j]>='0' and a[i][j]<='9');
int nj=j;
int v=0;
while(a[i][nj]>='0' and a[i][nj]<='9'){
v=v*10+(a[i][nj]-'0');
nj+=1;
}
lebs.pb(v);
queue<pii> que;
que.push({i,j});
usd[i][j]=v;
int sx=i,sy=j,tx=i,ty=j;
while(sz(que)){
auto top=que.front();
que.pop();
pii p=top;
rep(dir,4){
int ni=p.fi+di[dir];
int nj=p.se+dj[dir];
if(ok(ni,nj) and !usd[ni][nj]){
usd[ni][nj]=v;
sx=min(sx,ni);
sy=min(sy,nj);
tx=max(tx,ni);
ty=max(ty,nj);
if(a[ni][nj]=='+' or a[ni][nj]=='-' or a[ni][nj]=='|'){
}else{
que.push({ni,nj});
}
}
}
}
loc[v]={{sx,sy},{tx,ty}};
}
}
}
vec(vi) visited(h,vi(w));
auto find_path_=[&](auto self,int sx,int sy,int dir)->int{
assert(ok(sx,sy) and !visited[sx][sy]);
visited[sx][sy]=1;
if(a[sx][sy]=='-' or a[sx][sy]=='|'){
sx+=di[dir];
sy+=dj[dir];
return self(self,sx,sy,dir);
}else{
if(usd[sx][sy]!=0){
return usd[sx][sy];
}else{
assert(a[sx][sy]=='+');
if(dir==0){
if(ok(sx,sy-1) and a[sx][sy-1]=='-'){
dir=3;
}else{
dir=2;
}
}else{
dir=0;
}
sx+=di[dir];
sy+=dj[dir];
return self(self,sx,sy,dir);
}
}
};
vi pns;
auto dfs=[&](auto self,int v)->void{
pii s=loc[v].fi;
pii t=loc[v].se;
for(int i=t.fi;i>=s.fi;i--){
int l=s.se-1;
int r=t.se+1;
int u=-1;
if(ok(i,r) and a[i][r]=='-'){
u=find_path_(find_path_,i,r,2);
}else if(ok(i,l) and a[i][l]=='-'){
u=find_path_(find_path_,i,l,3);
}
if(u!=-1) self(self,u);
}
pns.pb(v);
};
dfs(dfs,1);
for(auto v:pns){
cout<<v<<" ";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
25 ms |
9300 KB |
Output is correct |
