Submission #1001838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001838		vjudge1	Robots (APIO13_robots)	C++17	10 / 100	1 ms	348 KiB

robots

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
//#include <iomanip>
#define ll long long
//#define int long long
#define pb push_back
// #define mp make_pair
// #define ff first
// #define ss second
// #define str string
// #define pii pair<int,int>
// #define sz(x) x.size()
#define all(x) x.begin(), x.end()
// #define vi vector<int>
// #define mii map<int,int>
// #define mll map<ll,ll>
// #define yes cout<<"YES\n";
// #define no cout<<"NO\n";
// #define yess cout<<"Yes\n";
// #define noo cout<<"No\n";
using namespace std;

int u[3][11][11];
char a[11][11];
int mn[11][11];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int k,n,m;

void dfs(int p,int i,int j,int x,int y,int s){
    if(i+x<=n && i+x>0 && j+y<=m && j+y>0 && a[i+x][j+y]!='x'){
        dfs(p,i+x,j+y,x,y,s);
    }
    else{
        if(u[p][i][j]<=s){
            return;
        }
        u[p][i][j]=min(u[p][i][j],s);
        for(int q=0;q<4;q++){
            if(i+dx[q]<=n && i+dx[q]>0 && j+dy[q]<=m && j+dy[q]>0 && a[i+dx[q]][j+dy[q]]!='x'){
                dfs(p,i+dx[q],j+dy[q],dx[q],dy[q],s+1);
            }
        }
    }
}

void solve(){
    cin>>k>>m>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            u[1][i][j]=100000;
            u[2][i][j]=100000;
            cin>>a[i][j];
            //cout<<a[i][j]<<" ";
        }
        //cout<<"\n";
    }
    //cout<<"\n\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='1'){
                u[1][i][j]=0;
                for(int q=0;q<4;q++){
                    if(i+dx[q]<=n && i+dx[q]>0 && j+dy[q]<=m && j+dy[q]>0 && a[i+dx[q]][j+dy[q]]!='x'){
                        dfs(1,i+dx[q],j+dy[q],dx[q],dy[q],1);
                    }
                }
            }
            if(a[i][j]=='2'){
                u[2][i][j]=0;
                for(int q=0;q<4;q++){
                    if(i+dx[q]<=n && i+dx[q]>0 && j+dy[q]<=m && j+dy[q]>0 && a[i+dx[q]][j+dy[q]]!='x'){
                        dfs(2,i+dx[q],j+dy[q],dx[q],dy[q],1);
                    }
                }
            }
        }
    }
    int ans=1000;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=min(ans,u[1][i][j]+u[2][i][j]);
        }
    }
    
    
    if(ans>=1000){
        cout<<-1;
    }
    else{
        cout<<ans;
    }
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int tests=1;
    //cin>>tests;
    for(int i=1;i<=tests;i++){
		//cout<<"TEST CASE : "<<i<<"\n";
		solve();
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40