Submission #991780

#TimeUsernameProblemLanguageResultExecution timeMemory
991780vjudge1Robots (APIO13_robots)C++17
0 / 100
1 ms604 KiB
#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 >= 1000) break; } if (ite >= 1000 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]); int ans = n * n * m * m; 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 ++) if (mat[x][y] == '1' and mat[nx][ny] == '2') ans = min(ans, dist[x][y][i][j] + dist[nx][ny][i][j]); if (ans == n * n * m * m) cout << -1 << endl; else cout << ans << endl; } /* 2 5 10 1......... AA...x.... ..A..x.... .....x.... .2C...A... */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...