Submission #101566

#	Time	Username	Problem	Language	Result	Execution time	Memory
101566		errorgorn	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1550 ms	781188 KiB

tracks

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> ii;
int r,c;
char arr[4005][4005];
bool pushed[4005][4005];
queue<ii> q;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
void print(){
    for (int x=1;x<=r;x++){
        for (int y=1;y<=c;y++){
            printf("%c",arr[x][y]);
        }
        printf("\n");
    }
    printf("\n");
}
void dfs(int i,int j,char a){
    for (int x=0;x<4;x++){
        if (i+dx[x]<1 || i+dx[x]>r || j+dy[x]<1 || j+dy[x]>c) continue;
        if (arr[i+dx[x]][j+dy[x]]==a){
            arr[i+dx[x]][j+dy[x]]='.';
            dfs(i+dx[x],j+dy[x],a);
        }
        else if (arr[i+dx[x]][j+dy[x]]!='.'){
            if (!pushed[i+dx[x]][j+dy[x]])q.push(ii(i+dx[x],j+dy[x])),pushed[i+dx[x]][j+dy[x]]=true;
        }
    }
}
int main(){
    char curr_animal='?';
    int ans=0;
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&r,&c);
    for (int x=1;x<=r;x++){
        getchar();
        for (int y=1;y<=c;y++){
            arr[x][y]=getchar();
        }
    }
    q.push(ii(1,1));
    q.push(ii(r,c));
    int a,b;
    while (!q.empty()){
        a=q.front().first,b=q.front().second,q.pop();
        //printf("%d %d\n",a,b);
        if (arr[a][b]=='.') continue;
        if (curr_animal!=arr[a][b]) curr_animal=arr[a][b],ans++;
        arr[a][b]='.';
        dfs(a,b,curr_animal);
    }
    printf("%d\n",ans);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&r,&c);
     ~~~~~^~~~~~~~~~~~~~

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