Submission #364880

#	Time	Username	Problem	Language	Result	Execution time	Memory
364880		fammo	Robots (APIO13_robots)	C++17	10 / 100	1 ms	364 KiB

robots

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define endl '\n'
#define int long long

const int  N = 10 + 2, MOD = 1000 * 1000 * 1000 + 7;
int n, h, w;
char a[N][N];
int vec[N][N][4];
vector<pii>adj[N][N];
int dis[2][N][N];
bool mark[2][N][N];
int H[] = {1,-1,0,0};
int G[] = {0,0,1,-1};
void bfs(int x, int y, bool b){
    queue<pii>q;
    q.push({x,y});
    mark[b][x][y] = 1;
    dis[b][x][y] = 0;
    while(!q.empty()){
        auto p = q.front();
        q.pop();int x = p.X, y = p.Y;
        for(auto po : adj[x][y]){
            int xx = po.X, yy = po.Y;
            if(!mark[b][xx][yy]){
                mark[b][xx][yy] = 1;
                dis[b][xx][yy] = dis[b][x][y] + 1;
                q.push({xx,yy});
            }
        }
    }return;
}
pii match(pii d, char c){
    if(c == 'A'){
        if(d.X == -1){
            return {0,-1};
        }if(d.X == 1){
            return {0, 1};
        }if(d.Y == -1){
            return {1, 0};
        }return {-1, 0};
    }
    if(d.X == -1)return {0,1};
    if(d.X == 1)return {0,-1};
    if(d.Y == -1)return{-1, 0};
    return{1,0};
}
pii move(int i, int j, pii d){
    //cout << i << "_"<<j<<"."<<d.X << "_"<<d.Y << "~~";
    int dx = d.X, dy = d.Y;
    int x =i, y = j;
    int lx = -1, ly = -1, rx = INT_MAX, ry = INT_MAX;
    if(dx != 0){
        if(dx==-1)
            lx = 0;
        else rx = h-1;
    }else{
        if(dy ==-1)
            ly = 0;
        else ry = w-1;
    }
    while(x>lx && x < rx && y > ly && y < ry && a[x][y] != 'C' && a[x][y] != 'A' && a[x+dx][y+dy]!='x'){
        x+=dx;
        y+=dy;
    }
    //if(x<=lx || x >= rx || y <=ly || y >=ry)return {i,j};
    if(a[x][y] == 'C' || a[x][y] == 'A'){
        auto D = match(d, a[x][y]);
        int xx = x + D.X, yy = y + D.Y;
        if(xx < 0 || xx > h-1 || yy < 0 || yy > w-1)return{x,y};
        return move(xx,yy,D);
    }return {x,y};
}
int32_t main(){
    fastio;
    ///auto t = clock();
    for(int i = 0; i < N; i ++)for(int j = 0; j < N; j ++)dis[0][i][j] = dis[1][i][j] = INT_MAX;
    cin >> n >> h >> w;
    int u[]={-1,-1}, v[] = {-1, -1};
    for(int i = 0; i < h; i ++){
        for(int j = 0; j < w; j ++){
            cin >> a[i][j];
            if(a[i][j] == '1') u[0] = i, u[1] = j;
            if(a[i][j] == '2') v[0] = i, v[1] = j;
        }
    }
    int H[] = {-1, 1, 0, 0};
    int G[] = {0, 0, -1, 1};
    for(int i = 0; i < h; i ++)for(int j = 0; j < w; j ++)if(a[i][j] != 'x'){
        for(int k = 0; k < 4; k ++){
            //cout << "SEE " << i << "," << j << ":[" << H[k] << "," << G[k] << "]->";
            auto p = move(i, j, {H[k], G[k]});//cout << "{" << p.X << "," << p.Y << "}"<< endl;
            if(p!=pii(i,j))adj[i][j].pb(p);
        }
    }
    /* for(int i = 0; i < h; i ++){
        for(int j =0 ; j < w; j ++){
            cout << i << "," << j << " : ";
            for(auto p : adj[i][j])cout << p.X << ',' << p.Y << ' ';
            cout << endl;
        }
    }*/
    //cout << "NNNOOOOWWW" << endl;
    bfs(u[0], u[1], 0);
    bfs(v[0], v[1], 1);int ans = INT_MAX;
    for(int i = 0; i < h; i ++)for(int j = 0; j < w; j ++){// cout << i << "," << j << ": " << dis[0][i][j] << ' ' << dis[1][i][j] << endl;
        ans = min(ans, dis[0][i][j] + dis[1][i][j]);}
    if(ans == INT_MAX)return cout << -1 << endl, 0;
    cout << ans;
    ///cout << clock() - t << "ms" << endl;
    return 0;
}

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