제출 #1136221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136221		ALTAKEXE	로봇 (APIO13_robots)	C++17	100 / 100	608 ms	124916 KiB

robots

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template <class T>
using pq = priority_queue<T, vector<T>, greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for (int i = 0; i < n; ++i)
#define rep2(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, a, b) for (int i = a; i < b; ++i)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(a) begin(a), end(a)
template <class T, class U>
bool chmin(T &a, const U &b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int INF = 0x33333333;

int n, w, h;
pii mem[500][500][4];
char s[501][501];
vector<pii> g[500][500];
int cost[10][10][500][500];
pii dfs(int x, int y, int d)
{
    if (x < 0)
        return {x + 1, y};
    if (y < 0)
        return {x, y + 1};
    if (x >= h)
        return {x - 1, y};
    if (y >= w)
        return {x, y - 1};
    if (s[x][y] == 'x')
        return {x + dx[d ^ 2], y + dy[d ^ 2]};
    if (mem[x][y][d] != pii{-1, -1})
        return mem[x][y][d];
    int d2 = d;
    if (s[x][y] == 'A')
    {
        d2 += 3;
        d2 &= 3;
    }
    else if (s[x][y] == 'C')
    {
        d2 += 1;
        d2 &= 3;
    }
    mem[x][y][d] = {-2, -2};
    return mem[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2);
}
void bfs(int from, int to)
{
    auto c = cost[from][to];
    rep(cen, from + 1, to) rep(h) rep(j, w) chmin(c[i][j], cost[from][cen][i][j] + cost[cen][to][i][j]);
    queue<tuplis> q;
    vector<tuplis> q2;
    rep(h) rep(j, w) if (c[i][j] != INF) q2.push_back({c[i][j], i, j});
    sort(all(q2), greater<tuplis>());
    while (q.size() || q2.size())
    {
        bool flag = 0;
        if (!q2.size())
            flag = 1;
        else if (q.size() && q.front()[0] < q2.back()[0])
            flag = 1;
        auto [cost, x, y] = flag ? q.front() : q2.back();
        if (flag)
            q.pop();
        else
            q2.pop_back();
        for (auto [x2, y2] : g[x][y])
            if (chmin(c[x2][y2], cost + 1))
            {
                q.push({c[x2][y2], x2, y2});
            }
    }
}
int main()
{
    memset(mem, 0xff, sizeof(mem));
    memset(cost, 0x33, sizeof(cost));
    scanf("%d%d%d", &n, &w, &h);
    rep(h) scanf("%s", s[i]);
    rep(h) rep(j, w) rep(d, 4) dfs(i, j, d);
    rep(h) rep(j, w) rep(d, 4) if (mem[i][j][d] != pii{-2, -2} && mem[i][j][d] != pii{i, j}) g[i][j].push_back(mem[i][j][d]);
    rep(h) rep(j, w) if (isdigit(s[i][j])) cost[s[i][j] - '1'][s[i][j] - '0'][i][j] = 0;
    rep(i, 1, n + 1) rep(j, 0, n + 1 - i) bfs(j, j + i);
    int ans = INF;
    rep(h) rep(j, w) chmin(ans, cost[0][n][i][j]);
    if (ans == INF)
        ans = -1;
    printf("%d\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'int main()':
robots.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d%d%d", &n, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:94:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     rep(h) scanf("%s", s[i]);
      |            ~~~~~^~~~~~~~~~~~

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