Türkçe

Çayırlık alanda bir noktadan dönmeden ulaşabildiği tüm noktalara kaç saniyede ulaşabileceğini hesaplayabiliyoruz.

• 1 birim = 1 saniye
• 2-3 birim = 2 saniye
• 4-6 birim = 3 saniye
• 7-10 birim = 4 saniye

Dano'nun bulunduğu nokta için bunu tüm yönlere uyguladığımızda çayırdaki noktaların bir kısmı için en iyi çözümü bulmuş oluyoruz. Aynı şekilde bunu sırayla çayırda yeni bulduğumuz alanlar için yaparsak, ve bulduğumuz yeni alanlara önceden ulaşabildiğimizden daha kısa sürede gidebildiklerimizi ve hiç gidemeyip şimdi ulaşabildiklerimizi sıraya atarsak tüm noktalar için o noktaya ulaşabileceğimiz en kısa süreyi buluruz. Buradaki tek sıkıntı ağaç olan noktalar. Ağaç olan noktalara giremediğimiz için bu noktalarla karşılaştığımızda artık bu noktanın ilerisine gidemiyoruz.

Özetlemek gerekirse, bir sıra (queue) oluşturuyoruz. Bu sırada en başta sadece Dano'nun bulunduğu nokta bulunuyor. Bu noktadan başlayarak ulaşabildiğimiz her noktanın direkt olarak yukarısında, aşağısında, sağında ve solunda olan tüm noktalara ulaşabileceğimiz en kısa süreyi buluyoruz, bu sırada her yeni kısa süre bulduğumuz noktayı yeniden sıraya atıyoruz. Sonuçta da Dano'nun Deno'ya ulaşabileceği en kısa süreyi yazdırıyoruz.

English

We can compute how many seconds does it take to reach all the points Dano can reach in the grass field without changing direction, from a certain point.

• 1 unit = 1 second
• 2-3 units = 2 seconds
• 4-6 units = 3 seconds
• 7-10 units = 4 seconds

If we do this for the initial point Dano stands on considering all directions, we get the optimal results for some of the points around. Similarly, we do this for the new areas that we have found and queue the points to which we have found a quicker path and the points we find a path which we previously could not reach to. This way we have the quickest path for each point. The only problematic points are the ones with trees on them. We cannot move past these points since we cannot enter the points with trees.

In summary, we create a queue that contains only the initial point. Then starting from this point, we calculate the minimum time it takes for each point that is directly in the upwards, downwards, left, or right of a point we can reach to. Meanwhile, we push every point that we find a new path to (this can be a previously unreached point or a point we just found a quicker path to). Then we print the minimum time it takes Dano to reach Deno.

Örnek Çözüm / Sample Solution

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n' 
#define all(x) x.begin(),x.end()
#define fill(x,y) memset((x),(y) ,sizeof(x))
#define type(x) __typeof(x.begin())
#define sz(x) ((int)x.size())
#define o ((f+l)/2)
#define dg(x) #x << ": " << x << " " 
#define umax(x,y) (x)=max((x),(y))
#define NEW(x) (x *)calloc(1,sizeof(x))
#define umin(x,y) (x)=min((x),(y))
#define tmax(x,y,z) max((x),max((y),(z))) 
#define tmin(x,y,z) min((x),min((y),(z))) 
#define PI (M_PI)

typedef long long int Lint;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<vector<Lint> > vv ;
const int maxn = 410 ;
const int maxm = 2e5 ;
const int mod = 1e9 + 7 ; 
const int inf = 1e8 ;


int N , M , K , cost[maxn], sx , sy , ex , ey  ;
int t[maxn][maxn] , C[maxn][maxn] ;

int main()
{
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;

    cin >> M >> N ;
    cin >> sy >> sx >> ey >> ex ;
    cin >> K ;
    for( int i=0 ; i<K ; i++ ){
        int x , y ;
        cin >> y >> x ;
        t[x][y] = 1 ;
    }

    for( int i=1,speed=1 ; i<=max(N,M) ;  ){
        for( int j=0 ; j<speed ; j++ ) cost[i+j] = speed ;
        i += speed ;
        speed++ ;
    }
    for( int i=0 ; i<maxn ; i++ )
        for( int j=0 ; j<maxn ; j++ )
            C[i][j] = inf ;

    priority_queue<iii,vector<iii>,greater<iii>> q;

    q.push( iii( 0 , ii(sx , sy) ) ) ;
    while( !q.empty() ){
        iii a = q.top();
        q.pop();
        int c = a.first ;
        int x = a.se.fi ;
        int y = a.se.se ;

        if( c > C[x][y] ) continue ;
        C[x][y] = c ;

        for( int i=1 ; x+i <= N ; i++ ){
            if( t[x+i][y] ) break ;
            if( C[x][y]+cost[i] < C[x+i][y] ) {
                C[x+i][y] = C[x][y]+cost[i] ;
                q.push( iii( C[x][y]+cost[i] , ii( x+i , y ) ) ) ;
            }
        }


        for( int i=1 ; x-i >= 1 ; i++ ){
            if( t[x-i][y] ) break ;
            if( C[x][y]+cost[i]< C[x-i][y] ) {
                C[x-i][y] = C[x][y]+cost[i] ;
                q.push( iii( C[x][y]+cost[i] , ii( x-i , y ) ) ) ;
            }
        }

        for( int i=1 ; y+i <= M ; i++ ){
            if( t[x][y+i] ) break ;
            if( C[x][y]+cost[i]< C[x][y+i] ) {
                C[x][y+i] = C[x][y]+cost[i] ;
                q.push( iii( C[x][y]+cost[i] , ii( x , y+i ) ) ) ;
            }
        }


        for( int i=1 ; y-i >= 1 ; i++ ){
            if( t[x][y-i] ) break ;
            if( C[x][y]+cost[i]< C[x][y-i] ) {
                C[x][y-i] = C[x][y]+cost[i] ;
                q.push( iii( C[x][y]+cost[i] , ii( x , y-i ) ) ) ;
            }
        }

    }
    if( C[ex][ey] == inf ) C[ex][ey] = -1 ;
    cout << C[ex][ey] << endl  ;

    return 0;
}