oj.uz

Submission #1002206

# Submission time Handle Problem Language Result Execution time Memory
1002206 2024-06-19T10:58:13 Z vjudge1 Robots (APIO13_robots) C++17
10 / 100
 0 ms 348 KB 
// #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 aa[4]={3,2,0,1};
int cc[4]={2,3,1,0};

int k,n,m;
int y=0;
void dfs(int p,int i,int j,int x,int y,int s,int pv,int w){
    //cout<<pv<<" \n";
    if(pv>100){
        return;
    }
    //if(y){cout<<i<<" "<<j<<"\n";}
    if(a[i][j]=='x')return;
    if(a[i][j]=='A'){
        //if(aa[w]==0)y=1;
        dfs(p,i,j,i+dx[aa[w]],j+dy[aa[w]],s,pv+1,aa[w]);
        return;
    }
    if(a[i][j]=='C'){
        dfs(p,i,j,i+dx[cc[w]],j+dy[cc[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,q);
            }
        }
    }
}

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(q==1)y=1;
                    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=10000;
    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]);
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<u[1][i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    // cout<<"\n\n";
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<u[2][i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    if(ans>=10000){
        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.0 / 10.0

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