oj.uz

답안 #259887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259887 2020-08-08T18:55:38 Z montermoner 로봇 (APIO13_robots) C++14
10 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
using Node = pair<int, int>;

char mat[505][505], mat2[505][505];
char clr[505][505];

int n, w, h;
bool visited[505][505];
int dist[505][505];

int xaxis[] = {1, -1, 0, 0}, yaxis[] = {0, 0, 1, -1};

bool check (int x, int y)
{
    return (x >= 1 && x <= w && y >= 1 && y <= h);
}

int main ()
{
    cin >> n >> w >> h;
    vector<pair<int, int>>v;
    for (int i = 1; i <= w; i++)
    {
        for (int j = 1; j <= h; j++)
        {
            cin >> mat[i][j];
            mat2[i][j] = mat[i][j];
            if (mat[i][j] >= '1' && mat[i][j] <= '9')
            {
                v.push_back({i, j});
            }
        }
    }

    if (abs((int)(mat[v[0].first][v[0].second] - mat[v[1].first][v[1].second])) != 1)
    {
        puts("-1");
        return 0;
    }

    queue<Node>q;
    q.push(v[0]);
    q.push(v[1]);

    visited[v[0].first][v[0].second] = 1;
    visited[v[1].first][v[1].second] = 1;

    clr[v[0].first][v[0].second] = mat[v[0].first][v[0].second];
    clr[v[1].first][v[1].second] = mat[v[1].first][v[1].second];

    dist[v[0].first][v[0].second] = 0;
    dist[v[1].first][v[1].second] = 0;

    int ans = 1e9;

    while (!q.empty())
    {

        Node node = q.front();
        q.pop();
        visited[node.first][node.second] = true;
        int nx = node.first, ny = node.second;
        char color = clr[nx][ny];

        //cout << nx << " " << ny << " " << color << ": " << endl;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j < 500; j++)
            {
                int xx = nx+(j*xaxis[i]), yy = ny+(j*yaxis[i]);
                //cout << xx << " " << yy << endl;
                if (!check(xx, yy) || mat[xx][yy] == 'x')
                {
                    if (j != 1)
                    {
                        int tx = nx+((j-1)*xaxis[i]), ty = ny+((j-1)*yaxis[i]);
                        if (visited[tx][ty] && clr[tx][ty] != color)
                        {
                            //cout << "found? " << tx << " " << ty << endl;
                            ans = min(ans, dist[tx][ty]+dist[nx][ny]+1);
                            goto heck;
                        }

                        if (visited[tx][ty])
                            goto heck;

                        visited[tx][ty] = true;
                        clr[tx][ty] = color;
                        mat2[tx][ty] = color;
                        dist[tx][ty] = dist[nx][ny] + 1;
                        q.push({tx, ty});
                    }
                    break;
                }
            }
            heck:
                continue;
        }
    }

        if (ans == 1e9)
        {
            cout << -1 << endl;
        } else {
            cout << ans << endl;
        }
        return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -