Submission #1166518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166518		wii	Robots (APIO13_robots)	C++20	0 / 100	52 ms	100168 KiB

robots

#include <bits/stdc++.h>
using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define endl "\n"
#define lx (id << 1)
#define rx (lx | 1)
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

const ll Linf = 0x3f3f3f3f3f3f3f3f;
const int Inf = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const int Lim = 1e6 + 5;

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

const int base = 3;
const int N = 5e2 + 5;
const int LOG = log2(N) + 1;
const int dx[] = {-1,  0, +1, 0};
const int dy[] = { 0, -1,  0, +1};
const int block = sqrt(N) + 2;

int k, n, m;
char a[N][N];

int vst[N][N][4];
pair<int, int> nxt[N][N][4];

bool good(int u, int v) {
    return 1 <= u && u <= n && 1 <= v && v <= m && a[u][v] != 'x';
}

pair<int, int> go(int u, int v, int d) {
    if (vst[u][v][d])
        return nxt[u][v][d];

    vst[u][v][d] = 1;
    nxt[u][v][d] = {-1, -1};

    int w = d;
    if (a[u][v] == 'A') {
        ++w; if (w > 3) w -= 4;
    }

    if (a[u][v] == 'C') {
        --w; if (w < 0) w += 4;
    }
    
    if (!good(u + dx[w], v + dy[w]))
        return {u, v};

    return nxt[u][v][d] = go(u + dx[w], v + dy[w], w);
}

int dp[N][N][10][10];
int dist[N][N];
void bfs(int l, int r) {
    foru(i, 1, n) foru(j, 1, m)
        dist[i][j] = Inf;
    
    priority_queue<pair<int, pii>> q;
    foru(i, 1, n) foru(j, 1, m) if (dp[l][r][i][j] != Inf) {
        q.emplace(-dp[l][r][i][j], make_pair(i, j));
        dist[i][j] = dp[l][r][i][j];
    }

    while (!q.empty()) {
        int w = -q.top().first;
        auto [u, v] = q.top().second;
        q.pop();

        minimize(dist[u][v], w);

        foru(d, 0, 3) {
            pair<int, int> th = go(u, v, d);

            if (th.first != -1)
            if (minimize(dist[th.first][th.second], w + 1))
                q.emplace(-w - 1, th);
        }
    }

    foru(i, 1, n) foru(j, 1, m)
        minimize(dp[l][r][i][j], dist[i][j]);
}

void merge(int l, int r, int p) {
    foru(i, 1, n) foru(j, 1, m)
        minimize(dp[l][p][i][j], dp[l][r][i][j] + dp[r + 1][p][i][j]);
}

void solve() {
    cin >> k >> m >> n;
    foru(i, 1, n) foru(j, 1, m)
        cin >> a[i][j];

    int Min = 9, Max = 0;
    foru(i, 1, n) foru(j, 1, m) if ('1' <= a[i][j] && a[i][j] <= '9') {
        minimize(Min, a[i][j] - '0');
        maximize(Max, a[i][j] - '0');
    }

    if (Max - Min + 1 != k)
        return cout << -1 << endl, void();

    foru(i, 1, n) foru(j, 1, m) if ('1' <= a[i][j] && a[i][j] <= '9')
        a[i][j] -= Min - 1;

    memset(dp, 0x3f, sizeof dp);
    foru(i, 1, n) foru(j, 1, m) if ('1' <= a[i][j] && a[i][j] <= '9')
        dp[a[i][j] - '0'][a[i][j] - '0'][i][j] = 0;

    ford(l, k, 1) foru(r, l, k) {
        if (!(l == 1 && r == k)) bfs(l, r);
        foru(p, r + 1, k)
            merge(l, r, p);

    /*
        cout << "? " << l << " " << r << endl;
        foru(i, 1, n) foru(j, 1, m)
            cout << setfill(' ') << setw(3) << (dp[l][r][i][j] == Inf ? -1 : dp[l][r][i][j]) << " \n"[j == m];
        cout << endl;
    */
        
    }

    int ans = Inf;
    foru(i, 1, n) foru(j, 1, m)
        minimize(ans, dp[1][k][i][j]);
    if (ans == Inf)
        ans = -1;
    cout << ans << endl;
}

signed main() {
    FastIO;

    #define task "test"
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    int ntest = 1;
    // cin >> ntest;
    while (ntest--) {
        //cout << "Case " << q << ": " << "\n"; 
        solve();
        //cout << "\n";
    }

    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:152:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:153:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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