Submission #101556

#	Time	Username	Problem	Language	Result	Execution time	Memory
101556		shenxy	Tracks in the Snow (BOI13_tracks)	C++11	7.19 / 100	2087 ms	31832 KiB

tracks

#include <cstdio>
#include <algorithm>
#include <queue>
#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};
int main() {
    int H, W, numani = 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]);
            if (mygrid[i][j] != '.') numani += 1;
        }
    }
    char curani = mygrid[0][0];
    int ans = 0, update = 0;
    while (numani > 0) {
        bool visited[H][W];
        memset(visited, false, sizeof(visited));
        visited[0][0] = true;
        mygrid[0][0] = '?';
        numani -= 1;
        queue<coord> bfsq;
        bfsq.push(coord(0, 0));
        while (!bfsq.empty()) {
            coord k = bfsq.front();
            bfsq.pop();
            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]] == curani || mygrid[k.first + dx[i]][k.second + dy[i]] == '?') {
                        if (!visited[k.first + dx[i]][k.second + dy[i]]) {
                            visited[k.first + dx[i]][k.second + dy[i]] = true;
                            bfsq.push(coord(k.first + dx[i], k.second + dy[i]));
                            if (mygrid[k.first + dx[i]][k.second + dy[i]] != '?') {
                                mygrid[k.first + dx[i]][k.second + dy[i]] = '?';
                                numani -= 1;
                                update = 1;
                            }
                        }
                    }
                }
            }
        }
        ans += update;
        if (curani == 'F') curani = 'R';
        else curani = 'F';
    }
    printf("%d", ans);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:12: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:16: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: 5 / 30
• Subtask 2: 2.1875 / 70