Submission #101598

#	Time	Username	Problem	Language	Result	Execution time	Memory
101598		shenxy	Tracks in the Snow (BOI13_tracks)	C++11	17.60 / 100	2067 ms	110552 KiB

tracks

#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int, int> coord;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
const int INF = 1000000000;
int main() {
    int H, W, ans = 0;
    scanf("%d %d", &H, &W);
    char mygrid[H][W];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            scanf(" %c", &mygrid[i][j]);
        }
    }
    int visited[H][W];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            visited[i][j] = INF;
        }
    }
    visited[0][0] = 0;
    deque<coord> bfsq;
    bfsq.push_back(coord(0, 0));
    while (!bfsq.empty()) {
        coord k = bfsq.front();
        bfsq.pop_front();
        for (int i = 0; i < 4; i++) {
            if (k.first + dx[i] >= 0 && k.first + dx[i] < H && k.second + dy[i] >= 0 && k.second + dy[i] < W) {
                if (mygrid[k.first + dx[i]][k.second + dy[i]] == mygrid[k.first][k.second]) {
                    if (visited[k.first + dx[i]][k.second + dy[i]] == INF) {
                        visited[k.first + dx[i]][k.second + dy[i]] = visited[k.first][k.second];
                        bfsq.push_front(coord(k.first + dx[i], k.second + dy[i]));
                    }
                } else if (mygrid[k.first + dx[i]][k.second + dy[i]] != '.') {
                    if (visited[k.first + dx[i]][k.second + dy[i]] == INF) {
                        visited[k.first + dx[i]][k.second + dy[i]] = visited[k.first][k.second] + 1;
                        bfsq.push_back(coord(k.first + dx[i], k.second + dy[i]));
                    }
                }
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            ans = max(ans, visited[i][j]);
        }
    }
    printf("%d", ans + 1);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &H, &W);
     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &mygrid[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 10.9375 / 70