提出 #14391815

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mod 1000000007
using namespace std;
ll binpow(ll x,ll y)/* (x^y)%p in O(log y) */{ll res=1;while (y > 0){if(y&1)res=(res*x);y = y>>1;x=(x*x);}return res;}
ll binpowmod(ll x,ll y,ll p)/* (x^y)%p in O(log y) */{ll res=1;x=x%p;while (y > 0){if(y&1)res=(res*x)%p;y = y>>1;x=(x*x)%p;}return res;}
ll mod_inverse(ll n,ll p)/* Returns n^(-1) mod p */{return binpowmod(n,p-2,p);}
ull gcd(ull x,ull y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}
bool comp(pair<int,int> x,pair<int,int> y)
{
    if(x.first<y.first)
        return true;
    else if(x.first==y.first)
        return x.second>y.second;
    else
        return false;
}
bool comp_pairs_by_s(pair<ll,ll> &x ,pair<ll,ll> &y)
{
    return x.second<y.second;
}
bool isPowerOfTwo (ll x)  
{  
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));  
}

class cmp      //comparator for priority_queue 
{               //declaration: priority_queue<int,vector<int>,cmp>
public:         
    bool operator()(pair<int,int> A,pair<int,int> B)
    {
        if(abs(A.first-A.second)==abs(B.first-B.second))
            return A.first>B.first;
        return abs(A.first-A.second)<abs(B.first-B.second);
    }
};
// int prime[100005]={0};
// void sieve(void)
// {
//  int i,j;
//  for(i=0;i<100005;i++)
//         prime[i]=1;
//  prime[0]=0,prime[1]=0;
//  for(i=2;i<=sqrt(100005);i++){
//      if(prime[i]){
//          for(j=i*i;j<100005;j+=i){
//              prime[j]=0;
//          }
//      }
//  }
    
// }
void swap(int &x,int &y){
    int temp=x;
    x=y;
    y=temp;
}

int dirx[]={1,-1,0,0};
int diry[]={0,0,1,-1};
vector<vector<int>> dp;
vector<string> pond;
vector<vector<bool>> vis;
bool check(int x,int y,int h,int w){
    if((x>=w) || (x<0) || (y>=h) || (y<0) || (pond[y][x]=='@') || (vis[y][x]==1))
        return false;
    else
        return true;

}

void findminstroke(pair<int,int> s,int h,int w,int k,int x2,int y2){
    if(dp[x2-1][y2-1]!=INT_MAX)
    {
        cout<<dp[x2-1][y2-1];
        exit(0);
    }
    vis[s.first][s.second]=1;
    int x=s.second;
    int y=s.first;
    bool flag[]={1,1,1,1};
    for(int i=1;i<=k;i++){
        if(!(flag[0] || flag[1] || flag[2] || flag[3]))
            break;
        //check horizontal dir
        if(x+i<w && pond[y][x+i]!='@' && flag[0] && !vis[y][x+i])
            dp[y][x+i]=min(dp[y][x+i],dp[y][x]+1);
        else
            flag[0]=0;
        if(x-i>=0 && pond[y][x-i]!='@' && flag[1] && !vis[y][x-i])
            dp[y][x-i]=min(dp[y][x-i],dp[y][x]+1);
        else
            flag[1]=0;
        //check vertical dir
        if(y+i<h && pond[y+i][x]!='@' && flag[2] && !vis[y+i][x])
            dp[y+i][x]=min(dp[y+i][x],dp[y][x]+1);
        else
            flag[2]=0;
        if(y-i>=0 && pond[y-i][x]!='@' && flag[3] && !vis[y-i][x])
            dp[y-i][x]=min(dp[y-i][x],dp[y][x]+1);
        else
            flag[3]=0;
    }
    //go for the childs
    for(int i=0;i<4;i++){
        x=s.second+dirx[i];
        y=s.first+diry[i];
        if(check(x,y,h,w))
            findminstroke(make_pair(y,x),h,w,k,x2,y2);
    }

}
void solve()
{   
    int h,w,k,x1,y1,x2,y2;
    cin>>h>>w>>k>>x1>>y1>>x2>>y2;
    pond.resize(h);
    dp.resize(h);
    vis.resize(h);
    for(int i=0;i<h;i++)
        dp[i].resize(w),vis[i].resize(w);

    for(int i=0;i<h;i++)
        cin>>pond[i];

    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++){
            dp[i][j]=INT_MAX;
            vis[i][j]=0;
        }

    dp[x1-1][y1-1]=0;
    if(pond[x1-1][y1-1]=='@' || pond[x2-1][y2-1]=='@'){
        cout<<-1;
        return;
    }
    findminstroke(make_pair(x1-1,y1-1),h,w,k,x2,y2);
    if(dp[x2-1][y2-1]==INT_MAX)
        cout<<-1;
    else
        cout<<dp[x2-1][y2-1];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

提出情報

ジャッジ結果