oj.uz

Submission #919697

# Submission time Handle Problem Language Result Execution time Memory
919697 2024-02-01T13:08:36 Z coding_snorlax Robots (APIO13_robots) C++14
10 / 100
 1 ms 600 KB 
#include<bits/stdc++.h>
using namespace std;
char G[15][15];
int dis_num[15][15][5];
pair<int,int> Place[15];
int Move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
deque<pair<int,int>> inqueue_place[5];
pair<int,int> direct(pair<int,int> place,int index){
    while(1){
        pair<int,int> tmp_place = {place.first+Move[index][0],place.second+Move[index][1]};
        if(G[tmp_place.first][tmp_place.second]=='x') return place;
        place = tmp_place;
    }
}
int main(){
    int n,m,k;
    cin>>k>>m>>n;
    for(int i=0;i<=m+1;i++) {G[0][i]='x';G[n+1][i]='x';}
    for(int i=0;i<=n+1;i++) {G[i][0]='x';G[i][m+1]='x';}
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            G[i][j]=s;
            if(s=='1') Place[1]={i,j};
            if(s=='2') Place[2]={i,j};
        }
    }
    for(int i=0;i<15;i++){
        for(int j=0;j<15;j++){
            for(int k=1;k<=2;k++){
                dis_num[i][j][k]=-1;
            }
        }
    }
    for(int i=1;i<=2;i++){
        dis_num[Place[i].first][Place[i].second][i]=0;
        inqueue_place[i].push_back(Place[i]);
        while((int)inqueue_place[i].size()){
            auto now = *(inqueue_place[i].begin());
            //cout << now.first << " " << now.second << "\n";
            inqueue_place[i].pop_front();
            for(int j=0;j<4;j++){
                auto tmp = direct(now,j);
                if(dis_num[tmp.first][tmp.second][i]==-1){
                    dis_num[tmp.first][tmp.second][i]=dis_num[now.first][now.second][i]+1;
                    inqueue_place[i].push_back(tmp);
                }
            }
        }
        //cout <<"now_size " << (int)inqueue_place.size() << " ";
    }
    /*
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            cout << setw(3) << dis_num[i][j][1] << " ";
        }
        cout << "\n";
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            cout << setw(3) << dis_num[i][j][2] << " ";
        }
        cout << "\n";
    }*/
    int answer = 1000;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(dis_num[i][j][1]!=-1 && dis_num[i][j][2]!=-1) answer = min(answer,dis_num[i][j][1]+dis_num[i][j][2]);
        }
    }
    if(answer!=1000) cout << answer;
    else cout << -1;
    //cout << dis_num[place_2.first][place_2.second];


}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -