oj.uz

Submission #991782

# Submission time Handle Problem Language Result Execution time Memory
991782 2024-06-03T06:50:47 Z vjudge1 Robots (APIO13_robots) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 15;
char mat[N][N];
int R, n, m, dist[N][N][N][N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool valid(int x, int y){
    return (x >= 0 and x < n and y >= 0 and y < m);
}

int main(){
    cin >> R >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> mat[i][j];

    memset(dist, 31, sizeof dist);
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < m; j ++){
            if (mat[i][j] == 'x') continue;

            dist[i][j][i][j] = 0;
            for (int d = 0; d < 4; d ++){
                int x = i;
                int y = j;
                int dir = d;

                int ite = 0;
                while (1){
                    ite++;
                    if (mat[x][y] == 'A')
                        dir = (dir - 1 + 4) % 4;
                    if (mat[x][y] == 'C')
                        dir = (dir + 1 + 4) % 4;

                    int nx = x + dx[dir];
                    int ny = y + dy[dir];

                    if (!valid(nx, ny))
                        break;

                    x = nx, y = ny;

                    if (ite >= 10000) break;
                }

                if (ite >= 10000 or (i == x and j == y)) continue;

                dist[i][j][x][y] = 1;
            }
        }
    }

    for (int ii = 0; ii < n * m; ii ++)
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
                for (int x = 0; x < n; x ++)
                    for (int y = 0; y < m; y ++)
                        for (int nx = 0; nx < n; nx ++)
                            for (int ny = 0; ny < m; ny ++)
                                dist[x][y][nx][ny] = min(dist[x][y][nx][ny], dist[x][y][i][j] + dist[i][j][nx][ny]);

    pair<int, int> A, B;
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < m; j ++){
            if (mat[i][j] == '1')
                A = {i, j};
            if (mat[i][j] == '2')
                B = {i, j};
        }
    }


    int ans = 1e8;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            ans = min(ans, dist[A.first][A.second][i][j] + dist[B.first][B.second][i][j]);

    if (ans >= 1e8)
        cout << -1 << endl;
    else
        cout << ans << endl; 
}

/*

2 5 10
1.........
AA...x....
..A..x....
.....x....
.2C...A...


*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -