Submission #158969

#	Time	Username	Problem	Language	Result	Execution time	Memory
158969		Kerim	Tracks in the Snow (BOI13_tracks)	C++17	8.33 / 100	245 ms	10876 KiB

tracks

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,m;
const int N=1e3+5;
char arr[N][N];
int dx[]={+1,-1,0,0};
int dy[]={0,0,+1,-1};
int vis[N][N];
int relax(queue<PII>q){
    if(q.empty())
        return 0;
    queue<PII>wow;
    while(!q.empty()){
        PII nd=q.front();q.pop();
    //    cout<<nd.ff<<" "<<nd.ss<<endl;
        for(int i=0;i<4;i++){
            int nx=nd.ff+dx[i];
            int ny=nd.ss+dy[i];
            if(nx>=1 and ny>=1 and nx<=n and ny<=m and !vis[nx][ny] and arr[nx][ny]==arr[nd.ff][nd.ss]){
                vis[nx][ny]=1;
                for(int j=0;j<4;j++){
                    int tox=nx+dx[j];
                    int toy=ny+dy[j];        
                    if(tox>=1 and toy>=1 and tox<=n and toy<=m and !vis[tox][toy] and arr[nx][ny]!=arr[tox][toy] and arr[tox][toy]!='*'){
                        wow.push(mp(tox,toy));
                        vis[tox][toy]=1;    
                    }
                }
                q.push(mp(nx,ny));    
            }
        }
    }
    return relax(wow)+1;
}
int main(){
   // freopen("file.in", "r", stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf(" %c",&arr[i][j]);
    vis[1][1]=1;queue<PII>uf;uf.push(mp(1,1));
    printf("%d\n",relax(uf));
    return 0;
}

Compilation message (stderr)

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

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