| Task: | Suunnistus |
| Sender: | a256 |
| Submission time: | 2025-01-18 14:06:50 +0200 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | 100 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 31 |
| #2 | ACCEPTED | 12 |
| #3 | ACCEPTED | 57 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | 3 | details |
| #2 | ACCEPTED | 0.05 s | 1, 2, 3 | details |
| #3 | ACCEPTED | 0.05 s | 1, 2, 3 | details |
| #4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #6 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
| #7 | ACCEPTED | 0.39 s | 2, 3 | details |
| #8 | ACCEPTED | 0.38 s | 2, 3 | details |
| #9 | ACCEPTED | 0.02 s | 2, 3 | details |
| #10 | ACCEPTED | 0.56 s | 3 | details |
| #11 | ACCEPTED | 0.58 s | 3 | details |
| #12 | ACCEPTED | 0.02 s | 3 | details |
| #13 | ACCEPTED | 0.40 s | 3 | details |
| #14 | ACCEPTED | 0.11 s | 2, 3 | details |
| #15 | ACCEPTED | 0.01 s | 3 | details |
| #16 | ACCEPTED | 0.00 s | 3 | details |
| #17 | ACCEPTED | 0.05 s | 2, 3 | details |
Code
#include <bits/stdc++.h>
using namespace std;
#define N 501
#define F first
#define S second
#define INF INT_MAX
int n,m,k,d[N][N][11],z[N][N];
string t[N];
priority_queue<pair<int,pair<int,int>>> q;
void haku(int c,int k){
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(t[i][j]==c){
if(k=='S'){
d[i][j][0]=0;
q.push({0,{i,j}});
}
else if(d[i][j][k-1]!=INF){
d[i][j][k]=d[i][j][k-1];
q.push({-d[i][j][k-1],{i,j}});
}
}
}
}
}
void haku2(int T){
while(q.size()){
auto P=q.top(); q.pop();
auto p=P.S;
int D=-P.F;
int i=p.F,j=p.S;
if(z[i][j]==T+1) continue;
z[i][j]=T+1;
if(i&&t[i-1][j]!='#'&&D+1<d[i-1][j][T]){
d[i-1][j][T]=D+1;
q.push({-D-1,{i-1,j}});
}
if(i<n-1&&t[i+1][j]!='#'&&D+1<d[i+1][j][T]){
d[i+1][j][T]=D+1;
q.push({-D-1,{i+1,j}});
}
if(j&&t[i][j-1]!='#'&&D+1<d[i][j-1][T]){
d[i][j-1][T]=D+1;
q.push({-D-1,{i,j-1}});
}
if(j<m-1&&t[i][j+1]!='#'&&D+1<d[i][j+1][T]){
d[i][j+1][T]=D+1;
q.push({-D-1,{i,j+1}});
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>k;
for(int i=0;i<n;++i) cin>>t[i];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
for(int t=0;t<10;++t){
d[i][j][t]=INF;
}
}
}
haku('S',0);
haku2(0);
for(int t=1;t<=k;++t){
haku('0'+t,t);
haku2(t);
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(t[i][j]=='E'){
if(d[i][j][k]==INF) cout<<"-1\n";
else cout<<d[i][j][k]<<'\n';
return 0;
}
}
}
}
Test details
Test 1
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 10 10 9 S293#35616 #662963731 54975451#7 5162589168 ... |
| correct output |
|---|
| 25 |
| user output |
|---|
| 25 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 0 ................................. |
| correct output |
|---|
| 301 |
| user output |
|---|
| 301 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 0 .#.........#.#..##..#............ |
| correct output |
|---|
| 253 |
| user output |
|---|
| 253 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 0 ...#......##.##.#.#..##..#..##... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 1 0 . . . . ... |
| correct output |
|---|
| 77 |
| user output |
|---|
| 77 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 1 500 0 ................................. |
| correct output |
|---|
| 166 |
| user output |
|---|
| 166 |
Test 7
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 ................................. |
| correct output |
|---|
| 3447 |
| user output |
|---|
| 3447 |
Test 8
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 .#........#..................#... |
| correct output |
|---|
| 4952 |
| user output |
|---|
| 4952 |
Test 9
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 ##.########.##########.#..#...... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 10
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 623475428948841896621266296765... |
| correct output |
|---|
| 205 |
| user output |
|---|
| 205 |
Test 11
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 7##814125813#3463#272134469457... |
| correct output |
|---|
| 157 |
| user output |
|---|
| 157 |
Test 12
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 ##67##36##5#3###67###8972#61##... |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |
Test 13
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 ....................#...#........ |
| correct output |
|---|
| 1313 |
| user output |
|---|
| 1313 |
Test 14
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 499 499 9 S#...#...#...#...#...#...#...#... |
| correct output |
|---|
| 1124942 |
| user output |
|---|
| 1124942 |
Test 15
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 500 1 9 1 6 1 3 ... |
| correct output |
|---|
| 332 |
| user output |
|---|
| 332 |
Test 16
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 1 500 9 996327784392827829434482995353... |
| correct output |
|---|
| 135 |
| user output |
|---|
| 135 |
Test 17
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 ................................. |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |