Submission #1061877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061877		sikai004	Tracks in the Snow (BOI13_tracks)	C++14	29.79 / 100	2101 ms	94400 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int row, col;
    cin>>row>>col;
    char meadow[row][col];
    int vis[row][col];
    for(int i=0;i<row;i++){
        fill(vis[i],vis[i]+col,0);
    }
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cin>>meadow[i][j];
        }
    }
    int numberoftimes=0;
    int dx[4] = {0, 0, -1, 1},dy[4] = {1, -1, 0, 0};          //dx and dy stores the way to get to the adjacent nodes
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            if(vis[i][j]==0 and (meadow[i][j]=='F' or meadow[i][j]=='R')){
                numberoftimes++;
                queue<pair<int, int> > q;                       //pair contains <y_coord, x_coord>
                char currchar=meadow[i][j];
                q.push(make_pair(i, j));    //push the starting node
                while (!q.empty()) {
                    int y = q.front().first;
                    int x = q.front().second;
                    vis[y][x]=1;
                    q.pop();
                    for (int i = 0; i < 4; i++) {
                        int new_y = y + dy[i], new_x = x + dx[i];              //adjacent nodes
                        if(new_y>=0 and new_y<row and new_x>=0 and new_x<col and meadow[new_y][new_x]==currchar){
                            char changedchar;
                            if(currchar=='F') changedchar='R';
                            else changedchar='F';
                            meadow[new_y][new_x]=changedchar;
                            q.push(make_pair(new_y, new_x));
                        }
                        //check if new node is within bounds, not visited and reachable (code for if it is not)
                    }
                }
            }        
        }
    }
    /*
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cout<<meadow[i][j]<<" ";
        }
        cout<<"\n";
    }
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cout<<vis[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    cout<<numberoftimes;
}

• Subtask 1: 16.666666666666668 / 30
• Subtask 2: 13.125 / 70