yukicoder No.34 - 砂漠の行商人

Source

ニコニコミュニティ
問題文

問題概要

$N$ 行 $N$ 列の盤面が与えられ,各マスには整数 $L_{ij}$ が書かれている.
また,初期体力 $V$ が与えられる.
上下左右に移動できるが,移動先のマスに書かれている整数だけ体力が減っていく.
体力が $0$ 以下になるような移動はできない.
出発点と目標地点が与えられるので,最小で何回移動すれば辿り着けるかを求める問題.
辿り着けないならそれを指摘する.

解法

マスと現在体力を状態として幅優先探索すれば良い.
ただし,体力が $2N \times \max(L_{ij})$ より大きければ,必ず最短移動回数(マンハッタン距離)でいけるので適当に枝刈りをする.
そうすれば,時間計算量 $O(N^3 L_{ij})$ 程度で計算できる.

C++によるスパゲッティなソースコード

#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: 2017年09月25日11時35分29秒
Last modified: 2014年12月05日00時57分30秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: