Submission #919697

#	Time	Username	Problem	Language	Result	Execution time	Memory
919697		coding_snorlax	Robots (APIO13_robots)	C++14	10 / 100	1 ms	600 KiB

robots

#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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40