답안 #636906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636906	2022-08-30T13:04:14 Z	ojoConmigo	Mecho (IOI09_mecho)	C++17	23 / 100	1000 ms	27928 KB

mecho

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

int n,s;
vector<vector<char>> grid;
vector<pair<int,int>> hives;
pair<int,int> root,obj;
vector<vector<int>> mapa;
vector<vector<bool>> visit;
vector<vector<int>> dp;

int sx[4] = {0,0,1,-1};
int sy[4] = {1,-1,0,0};

bool ok(int x, int y){
    return x < n && y < n && x >= 0 && y >= 0;
}

void bfs(){
    queue<pair<int,int>> cola;
    for(auto h : hives){
        cola.push(h);
    }
    while(cola.size()){
        auto q = cola.front();
        cola.pop();
        int x = q.first;
        int y = q.second;
        for(int i=0; i<4; i++){
            int nx = x + sx[i];
            int ny = y + sy[i];
            if(ok(nx,ny)){
                if(mapa[nx][ny] != -1)continue;
                if(grid[nx][ny] == 'G' || grid[nx][ny] == 'M'){
                    mapa[nx][ny] = mapa[x][y]+1;
                    cola.push({nx,ny});
                }
            }
        }
    }
}
/*
bool dfs(int x, int y,int k){
    if(x == obj.first && y == obj.second)return true;
    visit[x][y] = true;
    bool b = false;
    for(int i=0; i<4; i++){
        int nx = x+sx[i];
        int ny = y+sy[i];
        if(ok(nx,ny)){
            if(grid[nx][ny] == 'G' || grid[nx][ny] == 'D'){
                if(visit[nx][ny]) continue;
                if(mapa[nx][ny] > k){
                    b = max(b,dfs(nx,ny,k));
                }
            }
        }
    }
    return b;
}
*/
int dfs(int x, int y,int cost, int steps){
    //cout << x << " " << y << " " << cost << " " << steps << endl;
    //cout << dp[x][y] << endl;
    if(x == obj.first && y == obj.second) return 1e9;
    if(mapa[x][y] - cost < 0) return -1;
    if(dp[x][y] >= mapa[x][y] - cost) return -1;
    dp[x][y] = mapa[x][y] - cost;
    if(steps == s){
        steps = 0;
        cost++;
    }
    int sol = -1;
    for(int i=0; i<n; i++){
        int nx = x+sx[i];
        int ny = y+sy[i];
        if(ok(nx,ny)){
            if(grid[nx][ny] == 'G' || grid[nx][ny] == 'D'){
                int k = dfs(nx,ny,cost,steps+1);
                sol = max(sol,k);
                //cout << nx << " " << ny << " k: " << k << " sol: " << sol << endl;
            }
        }
    }
    //cout << x << " " << y << " " << cost << " sol: " << sol << endl;
    if(sol != -1) return min(sol,dp[x][y]);
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    grid.assign(n,vector<char> (n));
    mapa.assign(n,vector<int>(n,-1));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> grid[i][j];
            if(grid[i][j] == 'H'){
                hives.push_back({i,j});
                mapa[i][j] = 0;
            }
            if(grid[i][j] == 'M'){
                root = {i,j};
            }
            if(grid[i][j] == 'D'){
                obj = {i,j};
            }
        }
    }

    bfs();
    /*
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << mapa[i][j] << " ";
        }
        cout << endl;
    }
    */

    dp.assign(n,vector<int>(n,-1));
    cout << dfs(root.first,root.second,1,0) << endl;
    return 0;
    /*
    int lo = 1, hi = n*n, res = -1;
    while(lo <= hi){
        int mid = (lo+hi)/2;
        int k = dfs(root.first,root.second,s*mid);
        if(k - mid > res){
            res = mid;
            lo = mid+1;
        }else hi = mid-1;
    }
    cout << res << endl;
    */
}

Subtask #1

23.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Incorrect	0 ms	212 KB	Output isn't correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Correct	1 ms	212 KB	Output is correct
6	Incorrect	0 ms	212 KB	Output isn't correct
7	Execution timed out	1097 ms	7356 KB	Time limit exceeded
8	Incorrect	1 ms	212 KB	Output isn't correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	2 ms	280 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Incorrect	0 ms	212 KB	Output isn't correct
16	Correct	0 ms	212 KB	Output is correct
17	Incorrect	0 ms	212 KB	Output isn't correct
18	Correct	0 ms	212 KB	Output is correct
19	Incorrect	0 ms	340 KB	Output isn't correct
20	Correct	1 ms	212 KB	Output is correct
21	Incorrect	1 ms	340 KB	Output isn't correct
22	Correct	0 ms	340 KB	Output is correct
23	Incorrect	1 ms	340 KB	Output isn't correct
24	Correct	1 ms	340 KB	Output is correct
25	Incorrect	1 ms	340 KB	Output isn't correct
26	Correct	1 ms	340 KB	Output is correct
27	Incorrect	1 ms	340 KB	Output isn't correct
28	Correct	1 ms	340 KB	Output is correct
29	Incorrect	1 ms	340 KB	Output isn't correct
30	Correct	2 ms	340 KB	Output is correct
31	Incorrect	1 ms	468 KB	Output isn't correct
32	Correct	1 ms	468 KB	Output is correct
33	Incorrect	85 ms	3796 KB	Output isn't correct
34	Correct	86 ms	3796 KB	Output is correct
35	Execution timed out	1073 ms	5588 KB	Time limit exceeded
36	Execution timed out	1100 ms	4820 KB	Time limit exceeded
37	Correct	139 ms	4864 KB	Output is correct
38	Execution timed out	1091 ms	7124 KB	Time limit exceeded
39	Execution timed out	1091 ms	6100 KB	Time limit exceeded
40	Correct	209 ms	6056 KB	Output is correct
41	Execution timed out	1096 ms	9044 KB	Time limit exceeded
42	Execution timed out	1085 ms	7380 KB	Time limit exceeded
43	Correct	292 ms	7428 KB	Output is correct
44	Execution timed out	1098 ms	11092 KB	Time limit exceeded
45	Execution timed out	1096 ms	8916 KB	Time limit exceeded
46	Correct	445 ms	8904 KB	Output is correct
47	Execution timed out	1079 ms	13260 KB	Time limit exceeded
48	Execution timed out	1098 ms	10580 KB	Time limit exceeded
49	Correct	549 ms	10580 KB	Output is correct
50	Execution timed out	1090 ms	15820 KB	Time limit exceeded
51	Execution timed out	1086 ms	12384 KB	Time limit exceeded
52	Correct	736 ms	12304 KB	Output is correct
53	Execution timed out	1093 ms	18516 KB	Time limit exceeded
54	Execution timed out	1096 ms	14292 KB	Time limit exceeded
55	Correct	901 ms	14256 KB	Output is correct
56	Execution timed out	1055 ms	21456 KB	Time limit exceeded
57	Execution timed out	1092 ms	16332 KB	Time limit exceeded
58	Execution timed out	1084 ms	16188 KB	Time limit exceeded
59	Execution timed out	1084 ms	24652 KB	Time limit exceeded
60	Execution timed out	1089 ms	18484 KB	Time limit exceeded
61	Execution timed out	1062 ms	18508 KB	Time limit exceeded
62	Execution timed out	1090 ms	27928 KB	Time limit exceeded
63	Execution timed out	1093 ms	6336 KB	Time limit exceeded
64	Execution timed out	1094 ms	18980 KB	Time limit exceeded
65	Execution timed out	1094 ms	6796 KB	Time limit exceeded
66	Execution timed out	1096 ms	6476 KB	Time limit exceeded
67	Execution timed out	1090 ms	6412 KB	Time limit exceeded
68	Execution timed out	1086 ms	7004 KB	Time limit exceeded
69	Execution timed out	1098 ms	9072 KB	Time limit exceeded
70	Execution timed out	1062 ms	6652 KB	Time limit exceeded
71	Execution timed out	1081 ms	6536 KB	Time limit exceeded
72	Execution timed out	1086 ms	9168 KB	Time limit exceeded
73	Execution timed out	1090 ms	6352 KB	Time limit exceeded
74	Execution timed out	1089 ms	15116 KB	Time limit exceeded
75	Execution timed out	1088 ms	6348 KB	Time limit exceeded
76	Execution timed out	1086 ms	6244 KB	Time limit exceeded
77	Execution timed out	1087 ms	6612 KB	Time limit exceeded
78	Execution timed out	1097 ms	6472 KB	Time limit exceeded
79	Execution timed out	1097 ms	12868 KB	Time limit exceeded
80	Execution timed out	1057 ms	6396 KB	Time limit exceeded
81	Execution timed out	1093 ms	6272 KB	Time limit exceeded
82	Execution timed out	1089 ms	6896 KB	Time limit exceeded
83	Execution timed out	1081 ms	6432 KB	Time limit exceeded
84	Execution timed out	1091 ms	11060 KB	Time limit exceeded
85	Execution timed out	1091 ms	6484 KB	Time limit exceeded
86	Execution timed out	1085 ms	6348 KB	Time limit exceeded
87	Execution timed out	1083 ms	7160 KB	Time limit exceeded
88	Execution timed out	1097 ms	6740 KB	Time limit exceeded
89	Execution timed out	1067 ms	10128 KB	Time limit exceeded
90	Execution timed out	1092 ms	7268 KB	Time limit exceeded
91	Execution timed out	1090 ms	7628 KB	Time limit exceeded
92	Execution timed out	1088 ms	6916 KB	Time limit exceeded