Submission #31911

#	Time	Username	Problem	Language	Result	Execution time	Memory
31911		chonka	Tracks in the Snow (BOI13_tracks)	C++98	100 / 100	1493 ms	104988 KiB

tracks

#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>
using namespace std ;

#define MAXN 4007

int n , m ;
string a[ MAXN ] ;

int used[ MAXN ][ MAXN ] ;
int ans = 0 ;

int dx[ 4 ] = { 0 , 0 , 1 , -1 } ;
int dy[ 4 ] = { 1 , -1 , 0 , 0 } ;

void bfs ( ) {
    queue < pair < int , int > > q ;
    queue < pair < int , int > > aux ;
    int i , j ;
    used[ n ][ m ] = 1 ;
    q.push ( make_pair ( n , m ) ) ;
    while ( 1 ) {
        ans ++ ;
        while ( q.empty ( ) == false ) {
            pair < int , int > p = q.front ( ) ;
            q.pop ( ) ;
            int i ;
            for ( i = 0 ; i < 4 ; i ++ ) {
                int nx , ny ;
                nx = p.first + dx[ i ] ;
                ny = p.second + dy[ i ] ;
                if ( nx < 1 || n < nx ) { continue ; }
                if ( ny < 1 || m < ny ) { continue ; }
                if ( a[ nx ][ ny ] == '.' ) { continue ; }
                if ( used[ nx ][ ny ] != 0 ) { continue ; }
                used[ nx ][ ny ] = used[ p.first ][ p.second ] + 1 ;
                if ( a[ nx ][ ny ] == a[ p.first ][ p.second ] ) {
                    q.push ( make_pair ( nx , ny ) ) ;
                }
                else {
                    aux.push ( make_pair ( nx , ny ) ) ;
                }
            }
        }
        if ( aux.empty ( ) == true ) { break ; }
        while ( aux.empty ( ) == false ) {
            q.push ( aux.front ( ) ) ;
            aux.pop ( ) ;
        }
    }
}

void input ( ) {
    cin >> n >> m ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        cin >> a[ i ] ;
        a[ i ] = '#' + a[ i ] ;
    }
}

void solve ( ) {
    bfs ( ) ;
    printf ( "%d\n" , ans ) ;
}


int main ( ) {
    ios_base::sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

tracks.cpp: In function 'void bfs()':
tracks.cpp:21:9: warning: unused variable 'i' [-Wunused-variable]
     int i , j ;
         ^
tracks.cpp:21:13: warning: unused variable 'j' [-Wunused-variable]
     int i , j ;
             ^

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