oj.uz

Submission #580956

# Submission time Handle Problem Language Result Execution time Memory
580956 2022-06-22T06:54:45 Z 박상훈(#8359) Robots (APIO13_robots) C++17
30 / 100
 11 ms 7620 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Vertex{
    int x, y, d;
    Vertex(){}
    Vertex(int _x, int _y, int _d): x(_x), y(_y), d(_d) {}
}to[505][505][4];
char a[505][505];
bool visited[505][505][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, w, h;

void dfs(int x, int y, int d){
    visited[x][y][d] = 1;
    int nx, ny, nd = d;
    if (a[x][y]=='A') nd = (d+3)%4;
    if (a[x][y]=='C') nd = (d+1)%4;
    nx = x + dx[nd], ny = y + dy[nd];

    if (a[nx][ny]=='x') to[x][y][d] = Vertex(x, y, d);
    else if (visited[nx][ny][nd]) to[x][y][d] = to[nx][ny][nd];
    else{
        dfs(nx, ny, nd);
        to[x][y][d] = to[nx][ny][nd];
    }
}

void init(){
    for (int i=0;i<=h+1;i++) fill(a[i], a[i]+w+2, 'x');
    for (int i=1;i<=h;i++){
        scanf("%s", a[i]+1);
        a[i][w+1] = 'x';
    }

    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            for (int d=0;d<4;d++) if (!visited[i][j][d]) dfs(i, j, d);
        }
    }

    //printf("%d %d %d\n", to[2][6][1].x, to[2][6][1].y, to[2][6][1].d);
}

int dist[45][505][505];

void bfs(int t){
    int sx = -1, sy = -1;
    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            if (a[i][j]=='1'+t) sx = i, sy = j;
            dist[t][i][j] = 1e9;
        }
    }
    assert(sx!=-1);

    dist[t][sx][sy] = 0;
    queue<pair<int, int>> q;
    q.emplace(sx, sy);
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        for (int d=0;d<4;d++){
            int nx = to[x][y][d].x, ny = to[x][y][d].y;
            //if (!nx) printf("%d %d %d\n", x, y, d);
            assert(nx);

            if (dist[t][nx][ny]!=1e9) continue;
            dist[t][nx][ny] = dist[t][x][y] + 1;
            q.emplace(nx, ny);
        }
    }
}

int main(){

    scanf("%d %d %d", &n, &w, &h);
    init();

    bfs(0);
    bfs(1);
    int ans = 1e9;
    for (int i=1;i<=h;i++){
        for (int j=1;j<=w;j++){
            //if (dist[0][i][j]==0 && dist[1][i][j]==0) printf("%d %d\n", i, j);
            //if (dist[0][i][j]!=1e9)printf("%d ", dist[0][i][j]);
            //else printf("x ");
            ans = min(ans, dist[0][i][j] + dist[1][i][j]);
        }
        //printf("\n");
    }
    printf("%d\n", ans==1e9?-1:ans);
    return 0;
}

Compilation message

robots.cpp: In function 'void init()':
robots.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%s", a[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %d %d", &n, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 436 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Incorrect 11 ms 7620 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Incorrect 11 ms 7620 KB Output isn't correct
12 Halted 0 ms 0 KB -