AtCoder ABC051 C - Back and Forth

AtCoderに取り組んだ際のメモです。
問題ページはこちらです。

Point: 300
Difficulty: 852

考えたこと

・同じ座標を踏まずに始点と終点間を2回往復する必要がある
・sx < tx、sy < ty の制約があるので、（原則として）往路は"R"と"U"を、復路は"L"と"D"を選ぶことで最短経路を目指せる

・1回目の往復を最短にしようとすると、必ず (sx+1, sy+1)と(tx-1, ty-1) を踏んでしまう
・そのため、2回目を最短にしようと思っても、始点と終点で囲まれたグリッドの外側を回るしかなさそう
・外側を回って最短にしようとするなら、以下の経路が候補の1つになりそう
　・往路：グリッドの右下部分を通過する
　・復路：グリッドの左上部分を通過する

固定的な解答になってしまいますが、この条件のまま実装し、提出したところACしました。

提出したコード

提出ページ

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var sx, sy, tx, ty int
	fmt.Fscan(r, &sx)
	fmt.Fscan(r, &sy)
	fmt.Fscan(r, &tx)
	fmt.Fscan(r, &ty)

	dx := tx - sx
	dy := ty - sy

	var ans []string
	// 1回目往復
	// 往路
	for i := 0; i < dx; i++ {
		ans = append(ans, "R")
	}
	for i := 0; i < dy; i++ {
		ans = append(ans, "U")
	}
	// 復路
	for i := 0; i < dx; i++ {
		ans = append(ans, "L")
	}
	for i := 0; i < dy; i++ {
		ans = append(ans, "D")
	}

	// 2回目往復
	// 往路
	ans = append(ans, "D")
	for i := 0; i < dx+1; i++ {
		ans = append(ans, "R")
	}
	for i := 0; i < dy+1; i++ {
		ans = append(ans, "U")
	}
	ans = append(ans, "L")
	// 復路
	ans = append(ans, "U")
	for i := 0; i < dx+1; i++ {
		ans = append(ans, "L")
	}
	for i := 0; i < dy+1; i++ {
		ans = append(ans, "D")
	}
	ans = append(ans, "R")

	fmt.Println(strings.Join(ans, ""))
}

感想など

・決め打ちになりすぎているような気がする
・少し条件が異なる場合や、条件が変遷するような場合に対処できない

・今回は使わなかったけれど、経路探索の練習が必要