AcWing 3129. 不讲武德
原题链接
简单
作者:
ACMode
,
2021-01-12 17:00:36
,
所有人可见
,
阅读 570
#include<bits/stdc++.h>
using namespace std;
const int N = 200100;
int a[N], m[N], vst[N];
int main() {
freopen("morality.in", "r", stdin);
freopen("morality.out", "w", stdout);
int n;
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
queue<int> q;
q.push(1);
vst[1] = 1;
m[1] = 0;
int f;
while( !q.empty() ) {
f = q.front();
q.pop();
if( !vst[ a[f] ] ) { // 从 f 点魔法穿越
m[ a[f] ] = m[f] + 1;
vst[ a[f] ] = 1;
q.push(a[f]);
}
if(f > 1 && !vst[ f - 1 ]) { // 从 f 点到 f - 1 点
m[f - 1] = m[f] + 1;
vst[f - 1] = 1;
q.push(f - 1);
}
if(f < n && !vst[ f + 1 ]) { // 从 f 点到 f + 1 点
m[f + 1] = m[f] + 1;
vst[f + 1] = 1;
q.push(f + 1);
}
}
for(int i = 1; i <= n; i++) printf("%d ", m[i]);
return 0;
}