| Task: | Suunnistus |
| Sender: | a256 |
| Submission time: | 2025-01-18 13:56:50 +0200 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | 43 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 31 |
| #2 | ACCEPTED | 12 |
| #3 | WRONG ANSWER | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | WRONG ANSWER | 0.00 s | 3 | details |
| #2 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
| #3 | ACCEPTED | 0.02 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.10 s | 2, 3 | details |
| #8 | ACCEPTED | 0.10 s | 2, 3 | details |
| #9 | ACCEPTED | 0.01 s | 2, 3 | details |
| #10 | WRONG ANSWER | 0.14 s | 3 | details |
| #11 | WRONG ANSWER | 0.14 s | 3 | details |
| #12 | ACCEPTED | 0.02 s | 3 | details |
| #13 | WRONG ANSWER | 0.10 s | 3 | details |
| #14 | ACCEPTED | 0.11 s | 2, 3 | details |
| #15 | WRONG ANSWER | 0.01 s | 3 | details |
| #16 | WRONG ANSWER | 0.00 s | 3 | details |
| #17 | ACCEPTED | 0.02 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];
string t[N];
queue<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({i,j});
}
else if(d[i][j][k-1]!=INF){
d[i][j][k]=d[i][j][k-1];
q.push({i,j});
}
}
}
}
}
void haku2(int T){
while(q.size()){
auto p=q.front(); q.pop();
int i=p.F,j=p.S;
int D=d[i][j][T];
if(i&&t[i-1][j]!='#'&&d[i-1][j][T]==INF){
d[i-1][j][T]=D+1;
q.push({i-1,j});
}
if(i<n-1&&t[i+1][j]!='#'&&d[i+1][j][T]==INF){
d[i+1][j][T]=D+1;
q.push({i+1,j});
}
if(j&&t[i][j-1]!='#'&&d[i][j-1][T]==INF){
d[i][j-1][T]=D+1;
q.push({i,j-1});
}
if(j<m-1&&t[i][j+1]!='#'&&d[i][j+1][T]==INF){
d[i][j+1][T]=D+1;
q.push({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: WRONG ANSWER
| input |
|---|
| 10 10 9 S293#35616 #662963731 54975451#7 5162589168 ... |
| correct output |
|---|
| 25 |
| user output |
|---|
| 27 |
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: WRONG ANSWER
| input |
|---|
| 500 500 9 623475428948841896621266296765... |
| correct output |
|---|
| 205 |
| user output |
|---|
| 229 |
Test 11
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 500 500 9 7##814125813#3463#272134469457... |
| correct output |
|---|
| 157 |
| user output |
|---|
| 161 |
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: WRONG ANSWER
| input |
|---|
| 500 500 9 ....................#...#........ |
| correct output |
|---|
| 1313 |
| user output |
|---|
| 1755 |
Test 14
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 499 499 9 S#...#...#...#...#...#...#...#... |
| correct output |
|---|
| 1124942 |
| user output |
|---|
| 1124942 |
Test 15
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 500 1 9 1 6 1 3 ... |
| correct output |
|---|
| 332 |
| user output |
|---|
| 378 |
Test 16
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 1 500 9 996327784392827829434482995353... |
| correct output |
|---|
| 135 |
| user output |
|---|
| 177 |
Test 17
Group: 2, 3
Verdict: ACCEPTED
| input |
|---|
| 500 500 9 ................................. |
| correct output |
|---|
| -1 |
| user output |
|---|
| -1 |