yukicoder No.208 - 王将

Source

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

問題概要

上下左右に無限に広い $2$ 次元のマス目がある．
上下左右斜めに $1$ マス動ける駒が座標 $(0,0)$ にいて，座標 $(X,Y)$ まで移動したい．
ただし，座標 $(X_2,Y_2)$ には障害物があり，その座標に移動することはできない．
最小で何回移動したら目的のマスまで移動できるかを求める問題．

解法

障害物がないとしたら $\max(X,Y)$ 回の移動で移動できる．
上下と左右には独立に動け，上下も左右もずっと同じ方向に移動しないといけない場合，つまり，$X=Y$ の場合以外は，移動する経路は一意ではなく，途中に障害物があっても適当に迂回できる．
よって，$X=Y$ の場合で，最短経路上に障害物がある場合，つまり，$X_2 < X$ でかつ $X_2=Y_2$ の場合は，障害物を避けるためにもう $1$ 回余分に移動しなくてはいけない．

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);}
template <class T, class S> void reader(T *x, S *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);}
template<class T> void writerLn(T x){writer(x,'\n');}

int main(){
  int X, Y;
  int X2, Y2;

  reader(&X,&Y);
  reader(&X2,&Y2);

  if(X!=Y){
    writerLn(max(X,Y));
    return 0;
  }

  if(X2 < X && X2==Y2){
    writerLn(X+1);
  } else {
    writerLn(X);
  }

  return 0;
}

Current time: 2024年04月26日19時21分30秒
Last modified: 2015年05月26日23時18分52秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：