Submission #1001881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001881		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 ax[4]={-1,1,0,0};
int ay[4]={0,0,1,-1};
int aa[4]={2,3,1,0};
int cx[4]={1,-1,0,0};
int cy[4]={0,0,-1,1};
int cc[4]={3,2,0,1};

int k,n,m;

void dfs(int p,int i,int j,int x,int y,int s,int pv,int w){
    if(pv>200){
        return;
    }
    if(a[i][j]=='A'){
        dfs(p,i,j,ax[w],ay[w],s,pv+1,aa[w]);
        return;
    }
    if(a[i][j]=='C'){
        dfs(p,i,j,cx[w],cy[w],s,pv+1,cc[w]);
        return;
    }
    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,pv,w);
    }
    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,pv,w);
            }
        }
    }
}

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,0,q);
                    }
                }
            }
            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,0,q);
                    }
                }
            }
        }
    }
    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