標籤: hackerRank

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int dr[4]{1,0,-1,0},dc[4]{0,1,0,-1};

int dt[2005][2005];
string mp[2005];
bitset<2005> v[2005];

struct position{
    int r,c;
    bool operator==(position a){
        return r==a.r && c==a.c;
    }
};
bool operator<(position a,position b){
    return dt[a.r][a.c]>dt[b.r][b.c];
}

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

    int n,m,ans=INF;
    cin>>n>>m;

    for(int i=0;i<n;i++) for(int j=0;j<m;j++) dt[i][j]=INF;

    for(int i=0;i<n;i++){
        cin>>mp[i];
    }

    position ps,pe;
    cin>>ps.r>>ps.c;ps.r--;ps.c--;
    cin>>pe.r>>pe.c;pe.r--;pe.c--;
    dt[ps.r][ps.c]=0;

    priority_queue<position> bfs;
    bfs.push(ps);

    int ct;
    position now,next,mnPos;
    while(!bfs.empty()){
        now=bfs.top();
        bfs.pop();
        v[now.r][now.c]=1;
        for(int i=0;i<4;i++){
            next.r=now.r+dr[i];
            next.c=now.c+dc[i];
            if(next.r>=0 && next.c>=0 && next.r<n && next.c<m){
                ct=dt[now.r][now.c];
                if(mp[next.r][next.c]=='.')
                    ct++;
                if(pe==next)
                    ans=min(ans,ct);
                if(!v[next.r][next.c]){
                    v[next.r][next.c]=1;
                    dt[next.r][next.c]=ct;
                    bfs.push(next);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

vector<long> dt;

long msort(long l,long r){
    if(l>=r-1) return 0;
    long mid=(l+r)/2,j=mid;
    long sum=msort(l,mid)+msort(mid,r);
    long tmp[r-l],k=0;
    for(long i=l;i<mid;i++){
        while(j<r && dt[j]<dt[i]){
            tmp[k++]=dt[j++];
        }
        tmp[k++]=dt[i];
        sum+=j-mid;
    }
    while(j<r){
        tmp[k++]=dt[j++];
    }
    j=0;
    for(long i=l;i<r;i++){
        dt[i]=tmp[j];
        j++;
    }
    return sum;
}

int activityNotifications(vector<int> e, int d) {
    int ct=0;
    vector<int> m(205,0);
    for(int i=0;i<d;i++){
        m[e[i]]++;
    }
    for(int i=d;i<e.size();i++){
        int k=0,p=-1;
        for(int j=0;j<201;j++){
            k+=m[j];
            if(d&1){
                if(k>=d/2+1){
                    if(e[i]>=j*2) ct++;
                    break;
                }
            }else{
                if(k==d/2){
                    p=j;
                }else if(k>d/2){
                    if(p==-1){
                        if(e[i]>=j*2) ct++;
                    }else{
                        if(e[i]>=j+p) ct++;
                    }
                    break;
                }
            }
        }
        m[e[i]]++;
        m[e[i-d]]--;
    }
    return ct;
}