oj.uz

답안 #257224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257224 2020-08-03T22:49:12 Z aggu_01000101 로봇 (APIO13_robots) C++14
60 / 100
 623 ms 163840 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
//#define int long long
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
const int N = 500005;
string m[505];
int dp[505][505][10][10];
pair<int, int> final[505][505][4];
vector<pair<int, int>> adj[505][505];
int n, h, w;
int A(int x){
    return ((x+1)%4);
}
int C(int x){
    return ((x-1+4)%4);
}
bool valid(pair<int, int> x){
    if(x.first < 0 || x.second<0) return false;
    if(x.first >= h || x.second >= w) return false;
    return m[x.first][x.second] != 'x';
}
pair<int, int> update(pair<int, int> x, int dir){
    if(dir==0){
        x.first++;
        return x;
    }
    if(dir==1){
        x.second++;
        return x;
    }
    if(dir==2){
        x.first--;
        return x;
    }
    x.second--;
    return x;
}
pair<int, int> nxt(pair<int, int> curr, int &dir){
    if(m[curr.first][curr.second]=='C') dir = C(dir);
    else if(m[curr.first][curr.second]=='A') dir = A(dir);
    if(!valid(update(curr, dir))) return curr;
    return update(curr, dir);
}
pair<int, int> dfs(int i, int j, int dir){
    if(final[i][j][dir].first >=0){
        return final[i][j][dir];
    }
    else if(final[i][j][dir].first==-1){
        return {-1, -1};
    }
    final[i][j][dir] = {-1, -1};
    int currd = dir;
    pair<int, int> togo = nxt({i, j}, dir);
    if(togo.first == i && togo.second == j){
        //cout<<i<<" "<<j<<" in direction "<<dir<<" can't move"<<endl;
        return final[i][j][currd] = {i, j};
    }
    final[i][j][currd] = dfs(togo.first, togo.second, dir);
    //cout<<i<<" "<<j<<" in direction "<<currd<<" leads to "<<final[i][j][currd].first<<" "<<final[i][j][currd].second<<endl;
    return final[i][j][currd];
}
void BFS(pair<int, int> curr, int st){
    for(int i =0 ;i<h;i++){
        for(int j = 0;j<w;j++) dp[i][j][st][st] = INF;
    }
    dp[curr.first][curr.second][st][st] = 0;
    queue<pair<int, int>> q;
    q.push(curr);
    while(!q.empty()){
        curr = q.front();
        q.pop();
        for(pair<int, int> k: adj[curr.first][curr.second]){
            if(dp[k.first][k.second][st][st] < INF) continue;
            dp[k.first][k.second][st][st] = dp[curr.first][curr.second][st][st] + 1;
            q.push(k);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>w>>h;
    for(int i =0 ;i<h;i++) cin>>m[i];
    //dir 0 -> i++
    //dir 1 -> j++
    //dir 2 -> i--
    //dir 3 -> j--
    for(int i =0 ;i<h;i++){
        for(int j =0 ;j<w;j++){
            for(int k = 0;k<4;k++) final[i][j][k] = {-2, -2};
        }
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            for(int k = 0;k<4;k++){
                if(m[i][j]=='x') continue;
                pair<int, int> ta = dfs(i, j, k);
                //cout<<i<<" "<<j<<" "<<k<<" leads to ("<<ta.first<<", "<<ta.second<<")"<<endl;
                if(ta.first != -1){
                    adj[i][j].push_back(ta);
                }
            }
        }
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            if(m[i][j]=='A' || m[i][j]=='C' || m[i][j]=='x' || m[i][j]=='.') continue;
            int curr = m[i][j] - '0';
            BFS({i, j}, curr);
        }
    }
    vector<pair<int, int>> dPush[100000];
    for(int sz = 1;sz<n;sz++){
        for(int st = 1;(st+sz)<=n;st++){
            int sd = (st+sz);
            pair<int, int> toPush;
            int minCost = INF;
            set<int> allc;
            for(int i =0 ;i<h;i++){
                for(int j = 0;j<w;j++){
                    dp[i][j][st][sd] = INF;
                    for(int k = st;k<sd;k++) dp[i][j][st][sd] = min(dp[i][j][st][k] + dp[i][j][k+1][sd], dp[i][j][st][sd]);
                    if(dp[i][j][st][sd] < INF){
                        minCost = min(minCost, dp[i][j][st][sd]);
                        dPush[dp[i][j][st][sd]].push_back({i, j});
                        allc.insert(dp[i][j][st][sd]);
                    }
                }
            }
            if(minCost == INF) continue;
            queue<pair<int, int>> q;
            for(pair<int, int> j: dPush[minCost]) q.push({j.first, j.second});
            dPush[minCost].clear();
            while(!q.empty()){
                pair<int, int> curr = q.front();
                q.pop();
                int i = curr.first, j = curr.second;
                int cd = dp[i][j][st][sd];
                for(pair<int, int> nxt: dPush[cd+1]){
                    if(dp[nxt.first][nxt.second][st][sd] < (cd+1)) continue;
                    dp[nxt.first][nxt.second][st][sd] = cd + 1;
                    q.push(nxt);
                }
                dPush[cd+1].clear();
                for(pair<int, int> nxt: adj[i][j]){
                    if(dp[nxt.first][nxt.second][st][sd] <= (cd+1)) continue;
                    dp[nxt.first][nxt.second][st][sd] = cd + 1;
                    q.push({nxt.first, nxt.second});
                }
            }
            for(int k: allc) dPush[k].clear();
        }
    }
    int ans = INF;
    for(int i =0 ;i<h;i++){
        for(int j =0;j<w;j++){
            ans = min(ans, dp[i][j][1][n]);
        }
    }
    if(ans >= INF) ans = -1;
    cout<<ans<<endl;
}
/*

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

*/

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 5 ms 8704 KB Output is correct
3 Correct 6 ms 8704 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 5 ms 8832 KB Output is correct
6 Correct 5 ms 8704 KB Output is correct
7 Correct 5 ms 8704 KB Output is correct
8 Correct 5 ms 8704 KB Output is correct
9 Correct 5 ms 8704 KB Output is correct
10 Correct 5 ms 8832 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 5 ms 8704 KB Output is correct
3 Correct 6 ms 8704 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 5 ms 8832 KB Output is correct
6 Correct 5 ms 8704 KB Output is correct
7 Correct 5 ms 8704 KB Output is correct
8 Correct 5 ms 8704 KB Output is correct
9 Correct 5 ms 8704 KB Output is correct
10 Correct 5 ms 8832 KB Output is correct
11 Correct 245 ms 54512 KB Output is correct
12 Correct 40 ms 50440 KB Output is correct
13 Correct 98 ms 51576 KB Output is correct
14 Correct 449 ms 56736 KB Output is correct
15 Correct 159 ms 51960 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 5 ms 8704 KB Output is correct
3 Correct 6 ms 8704 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 5 ms 8832 KB Output is correct
6 Correct 5 ms 8704 KB Output is correct
7 Correct 5 ms 8704 KB Output is correct
8 Correct 5 ms 8704 KB Output is correct
9 Correct 5 ms 8704 KB Output is correct
10 Correct 5 ms 8832 KB Output is correct
11 Correct 245 ms 54512 KB Output is correct
12 Correct 40 ms 50440 KB Output is correct
13 Correct 98 ms 51576 KB Output is correct
14 Correct 449 ms 56736 KB Output is correct
15 Correct 159 ms 51960 KB Output is correct
16 Correct 368 ms 127232 KB Output is correct
17 Runtime error 623 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -