ABC051 C - Back and Forth

ある地点からある地点まで同じところ通らないで2往復するときにその最短経路の一つを求めろっていう問題（要約）。

問題は以下。

[考察]その１

スタートからゴールまでの経路を深さ優先探索（DFS）を使って列挙してその度にルートを更新していく？
また、visited行列を使って通ったか通っていないかを管理して通っていないところだけで探索をしていくイメージ。普通に計算量がエグくなりそうだし書き方もまだよくわかんねえなあって思って入力例とか見てたらそんなことしなくても簡単に一つくらいの最短経路くらい出せるなあって思って考察２へ。

[考察]その２

まあ少し書いてみればわかるんですが同じ経路通らないで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;
}

ながめも

競技プログラミングについて

ABC051 C - Back and Forth