$N$ 行 $N$ 列の盤面が与えられ,各マスには整数 $L_{ij}$ が書かれている.
また,初期体力 $V$ が与えられる.
上下左右に移動できるが,移動先のマスに書かれている整数だけ体力が減っていく.
体力が $0$ 以下になるような移動はできない.
出発点と目標地点が与えられるので,最小で何回移動すれば辿り着けるかを求める問題.
辿り着けないならそれを指摘する.
マスと現在体力を状態として幅優先探索すれば良い.
ただし,体力が $2N \times \max(L_{ij})$ より大きければ,必ず最短移動回数(マンハッタン距離)でいけるので適当に枝刈りをする.
そうすれば,時間計算量 $O(N^3 L_{ij})$ 程度で計算できる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
int N, V, SX, SY, GX, GY;
int L[111][111];
int dist[111][111][2222];
int q[22200222], q_st, q_size;
int main(){
int i, j, k, d, m, ni, nj, nk, nn;
int di[4]={-1,1,0,0}, dj[4]={0,0,-1,1};
int res;
reader(&N,&V); V--;
reader(&SY,&SX); SY--; SX--;
reader(&GY,&GX); GY--; GX--;
rep(i,N) rep(j,N) reader(L[i]+j);
if(V >= 2 * N * 9){
writer(abs(SX-GX)+abs(SY-GY),'\n');
return 0;
}
rep(i,N) rep(j,N) rep(k,V+1) dist[i][j][k] = -1;
dist[SX][SY][V] = 0;
q_st = q_size = 0;
q[q_st+q_size++] = (SX*N+SY)*(V+1)+V;
res = -1;
while(q_size){
m = q[q_st++]; q_size--;
k = m%(V+1); m /= V+1;
i = m/N; j = m%N;
rep(d,4){
ni = i + di[d];
nj = j + dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
nk = k - L[ni][nj];
if(nk < 0) continue;
if(dist[ni][nj][nk] >= 0) continue;
nn = (ni*N+nj)*(V+1)+nk;
dist[ni][nj][nk] = dist[i][j][k] + 1;
if(ni==GX && nj==GY){ res = dist[ni][nj][nk]; break; }
q[q_st+q_size++] = nn;
}
if(res >= 0) break;
}
writer(res,'\n');
return 0;
}
Current time: 2024年03月29日16時42分40秒
Last modified: 2014年12月05日00時57分30秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る
Logged in as: unknown user (not login)