Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.7 kB
6
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MAXN=1e3+1;
ll n,m,move_x[]={1,-1,0,0},move_y[]={0,0,1,-1},ans[MAXN][MAXN],end_y,end_x;
char a[MAXN][MAXN];

void ditcha(ll y,ll x){
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>>> pos;
    pos.push({0,{y,x}});
    ans[y][x]=0;
    while(!pos.empty()){
        pair <ll,pair<ll,ll>> top=pos.top();
        pos.pop();
        ll dist=top.first, old_y=top.second.first, old_x=top.second.second;
        if(dist > ans[old_y][old_x])   continue;
        for(ll i=0 ; i<4 ; i++){
            ll new_y = old_y + move_y[i];
            ll new_x = old_x + move_x[i];
            if(new_x > m || new_x < 1)  continue;
            if(new_y > n || new_y < 1)  continue;
            if(ans[new_y][new_x] > dist + (a[new_y][new_x] - '0')){
                ans[new_y][new_x] = dist + (a[new_y][new_x] - '0');            
                pos.push({ans[new_y][new_x],{new_y,new_x}});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("TEST.inp","r",stdin);
    freopen("TEST.out","w",stdout);
    ll str_x,str_y;
    cin >> n >> m;
    for(ll i=1 ; i<=n ; i++){
        for(ll j=1 ; j<=m ; j++){
            ans[i][j] = INT_MAX;
            cin >> a[i][j];
            if(a[i][j] == 'G'){
                a[i][j] = '0';
                str_x = j;
                str_y = i;
            }
            if(a[i][j] == 'R'){
                a[i][j] = '0';
                end_y = i;
                end_x = j;
            }
        }
    }
    ditcha(str_y,str_x);
    cout << ans[end_y][end_x];
}
Leave a Comment