oj.uz

Submission #72304

# Submission time Handle Problem Language Result Execution time Memory
72304 2018-08-26T06:58:05 Z 동진의 (#2167, kdk3776, define_chan, Jinpari) Aquatic Labyrinth (FXCUP3_aqua) C++17
36 / 100
 3000 ms 12468 KB 
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<list>
#include<cstring>
#include<algorithm>
#define fio ios_base::sync_with_stdio(0)
//배열크기 확인
#define MAXNUM 910
using namespace std;

struct point{
    int x, y, cost;
    point operator +(const point & a) const{
        return {x + a.x, y + a.y, cost};
    }
};

int main(){
    int n;
    int ans=1000000000;
    int cost[MAXNUM][MAXNUM]={0};
    char map[MAXNUM][MAXNUM]={0};
    queue<point> q;
    memset(cost, 40, sizeof(cost));
    point dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
        scanf("%s", map[i]+1);
    for (int i=0; i<=n+1; i++) {map[i][0] = map[i][n+1] = map[0][i] = map[n+1][i] = '#';}
    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (map[i][j] == 'M') {
                q.push({j, i, 0});
                cost[i][j] = 0;
            }
        }
    }
    
    while (!q.empty()) {
        point cur = q.front(); q.pop();
        for (int i=0; i<4; i++) {
            int cnt=0;
            point next = cur;
            while (map[next.y][next.x] != 'W' && map[next.y][next.x] != '#') {
                next = next + dir[i];
            }
            while (map[next.y][next.x] == 'W') {
                cnt++;
                next = next + dir[i];
            }
            next.cost += cnt * cnt;
            
            while (map[next.y][next.x] == '.' || map[next.y][next.x] == 'H') {
                if (cost[next.y][next.x] > next.cost) {
                    cost[next.y][next.x] = next.cost;
                    if (map[next.y][next.x] == 'H') {
                        ans = min(ans, cost[next.y][next.x]);
                        break;
                    }
                    q.push(next);
                }
                next = next + dir[i];
            }
        }
    }
    
    printf("%d\n", ans > 999999999 ? -1 : ans);
    
    return 0;
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
aqua.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", map[i]+1);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 6 ms 4452 KB Output is correct
3 Correct 7 ms 4536 KB Output is correct
4 Correct 6 ms 4536 KB Output is correct
5 Correct 7 ms 4612 KB Output is correct
6 Correct 7 ms 4612 KB Output is correct
7 Correct 26 ms 4700 KB Output is correct
8 Correct 27 ms 4788 KB Output is correct
9 Correct 6 ms 4788 KB Output is correct
10 Correct 6 ms 4788 KB Output is correct

Subtask #2
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 6 ms 4452 KB Output is correct
3 Correct 7 ms 4536 KB Output is correct
4 Correct 6 ms 4536 KB Output is correct
5 Correct 7 ms 4612 KB Output is correct
6 Correct 7 ms 4612 KB Output is correct
7 Correct 26 ms 4700 KB Output is correct
8 Correct 27 ms 4788 KB Output is correct
9 Correct 6 ms 4788 KB Output is correct
10 Correct 6 ms 4788 KB Output is correct
11 Correct 1214 ms 6560 KB Output is correct
12 Correct 12 ms 6560 KB Output is correct
13 Execution timed out 3010 ms 12468 KB Time limit exceeded
14 Halted 0 ms 0 KB -