#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
int n,m;
char map[420][420];
int par;
int chk[420][420];
int dfs(int x,int y)
{
if(x<=0||x>n||y<=0||y>m||chk[x][y]==par+1)
return 0;
chk[x][y]=par;
bool ch[4];
for(int i=0;i<4;i++)
ch[i]=0;
int ans=2;
for(int i=-2;i<2;i++)
{
int nx=x+i%2;
int ny=y+(i+1)%2;
if(chk[nx][ny]!=par)
ch[i+2]=1;
}
if(map[x][y]=='N')
{
if(ch[1]&&ch[2])
{
int r=dfs(x-1,y);
ans+=r;
if(r==-1)
return -1;
r=dfs(x,y+1);
ans+=r;
if(r==-1)
return -1;
}
else if(ch[0]&&ch[3])
{
int r=dfs(x,y-1);
ans+=r;
if(r==-1)
return -1;
r=dfs(x+1,y);
ans+=r;
if(r==-1)
return -1;
}
else
return -1;
}
else
{
if(ch[0]&&ch[1])
{
int r=dfs(x,y-1);
ans+=r;
if(r==-1)
return -1;
r=dfs(x-1,y);
ans+=r;
if(r==-1)
return -1;
}
else if(ch[2]&&ch[3])
{
int r=dfs(x,y+1);
ans+=r;
if(r==-1)
return -1;
r=dfs(x+1,y);
ans+=r;
if(r==-1)
return -1;
}
else
return -1;
}
chk[x][y]=par+1;
return ans;
}
int aans[420][420];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=0;i++<n;)
for(int j=0;j++<m;)
cin>>map[i][j],aans[i][j]=inf;
for(int i=0;i++<n;)
{
par+=2;
int ans=0;
for(int j=0;j++<m;)
{
if(chk[i][j]==par+1)
{
aans[i][j]=min(aans[i][j],ans);
continue;
}
chk[i][j]=par;
int r=dfs(map[i][j]=='N'?i+1:i-1,j);
if(r==-1)
break;
aans[i][j]=min(aans[i][j],ans+=r+2);
chk[i][j]=par+1;
}
}
for(int i=0;i++<n;)
{
par+=2;
int ans=0;
for(int j=m;j>0;j--)
{
if(chk[i][j]==par+1)
{
aans[i][j]=min(aans[i][j],ans);
continue;
}
chk[i][j]=par;
int r=dfs(map[i][j]=='Z'?i+1:i-1,j);
if(r==-1)
break;
aans[i][j]=min(aans[i][j],ans+=r+2);
chk[i][j]=par+1;
}
}
for(int j=0;j++<m;)
{
par+=2;
int ans=0;
for(int i=0;i++<n;)
{
if(chk[i][j]==par+1)
{
aans[i][j]=min(aans[i][j],ans);
continue;
}
chk[i][j]=par;
int r=dfs(i,map[i][j]=='N'?j+1:j-1);
if(r==-1)
break;
aans[i][j]=min(aans[i][j],ans+=r+2);
chk[i][j]=par+1;
}
}
for(int j=0;j++<m;)
{
par+=2;
int ans=0;
for(int i=n;i>0;i--)
{
if(chk[i][j]==par+1)
{
aans[i][j]=min(aans[i][j],ans);
continue;
}
chk[i][j]=par;
int r=dfs(i,map[i][j]=='Z'?j+1:j-1);
if(r==-1)
break;
aans[i][j]=min(aans[i][j],ans+=r+2);
chk[i][j]=par+1;
}
}
for(int i=0;i++<n;)
for(int j=0;j++<m;cout<<(j==m?'\n':' '))
cout<<(aans[i][j]==inf?-1:aans[i][j]);
cout.flush();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
512 KB |
Output is correct |
8 |
Correct |
9 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
9 ms |
512 KB |
Output is correct |
11 |
Correct |
10 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
13 |
Correct |
9 ms |
512 KB |
Output is correct |
14 |
Correct |
10 ms |
512 KB |
Output is correct |
15 |
Correct |
7 ms |
512 KB |
Output is correct |
16 |
Correct |
5 ms |
512 KB |
Output is correct |
17 |
Correct |
5 ms |
512 KB |
Output is correct |
18 |
Correct |
8 ms |
512 KB |
Output is correct |
19 |
Correct |
6 ms |
512 KB |
Output is correct |
20 |
Correct |
4 ms |
512 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
6 ms |
512 KB |
Output is correct |
23 |
Correct |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
9 ms |
512 KB |
Output is correct |
25 |
Correct |
9 ms |
640 KB |
Output is correct |
26 |
Correct |
9 ms |
512 KB |
Output is correct |
27 |
Correct |
9 ms |
640 KB |
Output is correct |
28 |
Correct |
9 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
512 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
512 KB |
Output is correct |
8 |
Correct |
9 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
9 ms |
512 KB |
Output is correct |
11 |
Correct |
10 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
13 |
Correct |
9 ms |
512 KB |
Output is correct |
14 |
Correct |
10 ms |
512 KB |
Output is correct |
15 |
Correct |
7 ms |
512 KB |
Output is correct |
16 |
Correct |
5 ms |
512 KB |
Output is correct |
17 |
Correct |
5 ms |
512 KB |
Output is correct |
18 |
Correct |
8 ms |
512 KB |
Output is correct |
19 |
Correct |
6 ms |
512 KB |
Output is correct |
20 |
Correct |
4 ms |
512 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
6 ms |
512 KB |
Output is correct |
23 |
Correct |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
9 ms |
512 KB |
Output is correct |
25 |
Correct |
9 ms |
640 KB |
Output is correct |
26 |
Correct |
9 ms |
512 KB |
Output is correct |
27 |
Correct |
9 ms |
640 KB |
Output is correct |
28 |
Correct |
9 ms |
640 KB |
Output is correct |
29 |
Correct |
6 ms |
384 KB |
Output is correct |
30 |
Correct |
6 ms |
1792 KB |
Output is correct |
31 |
Correct |
53 ms |
2424 KB |
Output is correct |
32 |
Correct |
36 ms |
2424 KB |
Output is correct |
33 |
Correct |
11 ms |
1792 KB |
Output is correct |
34 |
Correct |
3013 ms |
2796 KB |
Output is correct |
35 |
Correct |
2506 ms |
2464 KB |
Output is correct |
36 |
Correct |
39 ms |
1912 KB |
Output is correct |
37 |
Correct |
3469 ms |
3064 KB |
Output is correct |
38 |
Correct |
2768 ms |
3088 KB |
Output is correct |
39 |
Correct |
3300 ms |
3064 KB |
Output is correct |
40 |
Correct |
5237 ms |
3160 KB |
Output is correct |
41 |
Correct |
2731 ms |
2140 KB |
Output is correct |
42 |
Correct |
4212 ms |
3320 KB |
Output is correct |
43 |
Correct |
4217 ms |
3320 KB |
Output is correct |
44 |
Correct |
4273 ms |
3320 KB |
Output is correct |
45 |
Correct |
2893 ms |
2960 KB |
Output is correct |
46 |
Correct |
2096 ms |
3064 KB |
Output is correct |
47 |
Correct |
2570 ms |
2936 KB |
Output is correct |
48 |
Correct |
1421 ms |
2608 KB |
Output is correct |
49 |
Correct |
2001 ms |
2940 KB |
Output is correct |
50 |
Correct |
2220 ms |
2936 KB |
Output is correct |
51 |
Correct |
1988 ms |
3064 KB |
Output is correct |
52 |
Correct |
1734 ms |
3064 KB |
Output is correct |
53 |
Correct |
1729 ms |
2952 KB |
Output is correct |
54 |
Correct |
1766 ms |
2948 KB |
Output is correct |
55 |
Correct |
1883 ms |
2952 KB |
Output is correct |
56 |
Correct |
1872 ms |
3064 KB |
Output is correct |
57 |
Correct |
1300 ms |
2636 KB |
Output is correct |
58 |
Correct |
4389 ms |
3220 KB |
Output is correct |
59 |
Correct |
4308 ms |
3168 KB |
Output is correct |
60 |
Correct |
3024 ms |
2704 KB |
Output is correct |
61 |
Correct |
4179 ms |
3116 KB |
Output is correct |
62 |
Correct |
4687 ms |
13048 KB |
Output is correct |
63 |
Correct |
4621 ms |
13048 KB |
Output is correct |