ABC051 C - Back and Forth
ABC051 C - Back and Forth
ある地点からある地点まで同じところ通らないで2往復するときにその最短経路の一つを求めろっていう問題(要約)。
問題は以下。
- [考察]その1
スタートからゴールまでの経路を深さ優先探索(DFS)を使って列挙してその度にルートを更新していく?
また、visited行列を使って通ったか通っていないかを管理して通っていないところだけで探索をしていくイメージ。普通に計算量がエグくなりそうだし書き方もまだよくわかんねえなあって思って入力例とか見てたらそんなことしなくても簡単に一つくらいの最短経路くらい出せるなあって思って考察2へ。
- [考察]その2
まあ少し書いてみればわかるんですが同じ経路通らないで2往復ってそんなにパターンなくて、はい。公式の解説みれば簡単にわかると思うのでリンクだけ。
https://img.atcoder.jp/abc051/editorial.pdf
コードは以下。Submission #4244495 - AtCoder Beginner Contest 051
#include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i<int(N);++i) int main() { int sx,sy,tx,ty,dx,dy; cin>>sx>>sy>>tx>>ty; string ans=""; dx=abs(tx-sx); dy=abs(ty-sy); //root1 rep(i,dy)ans+='U'; rep(i,dx)ans+='R'; //root2 rep(i,dy)ans+='D'; rep(i,dx)ans+='L'; //root3 ans+='L'; rep(i,dy+1)ans+='U'; rep(i,dx+1)ans+='R'; ans+='D'; //root4 ans+='R'; rep(i,dy+1)ans+='D'; rep(i,dx+1)ans+='L'; ans+='U'; cout<<ans<<endl; }