Submission #1120728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120728		coolboy19521	Tracks in the Snow (BOI13_tracks)	C++17	86.88 / 100	2110 ms	114132 KiB

tracks

#pragma GCC optimize("Ofast")
#include "iostream"
#include "queue"
#include "tuple"
using namespace std;
 
const short mxN = 4001;
 
int cl[mxN][mxN];
short g[mxN][mxN];
short H, W;
 
bool legal(short i, short j) {
    return 0 <= i && 0 <= j && i < H && j < W && 2 != g[i][j];
}
 
int main() {
    cin >> H >> W;
 
    for (int i = 0; i < H; i ++) {
        char s[W];
        scanf("%s", &s);
        for (int j = 0; j < W; j ++) {
            char c = s[j];
            if ('F' == c) {
                g[i][j] = 1;
            } else if ('.' == c) {
                g[i][j] = 2;
            }
        }
    }
 
    priority_queue<tuple<int,short,short>> pq;
    pq.emplace(-1, 0, 0);
    cl[0][0] = -1;
 
    short dx[] = {0, 0, 1, -1};
    short dy[] = {1, -1, 0, 0};
 
    while (!pq.empty()) {
        auto [c, i, j] = pq.top();
        pq.pop();
        for (int k = 0; k < 4; k ++) {
            short l = i + dx[k];
            short o = j + dy[k];
            if (legal(l, o) && 0 == cl[l][o]) {
                if (g[l][o] == g[i][j]) {
                    cl[l][o] = c;
                    pq.emplace(c, l, o);
                } else {
                    cl[l][o] = c - 1;
                    pq.emplace(c - 1, l, o);
                }
            }
        }
        if (pq.empty()) {
            printf("%d\n", -c);
        }
    }
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:22:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[W]' [-Wformat=]
   22 |         scanf("%s", &s);
      |                ~^   ~~
      |                 |   |
      |                 |   char (*)[W]
      |                 char*
tracks.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%s", &s);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 56.875 / 70