[BOJ]10164番:グリッド上のパス(Go,Golang)

10805 ワード
baekjoon algorithm go テキストリンク
質問リンク:白駿10164号

[質問へのアクセス]


ロボットは右か下しか歩けないので、dpで解くことができるようです.
まず,グリッドを表すdp配列はint型numとbool型checkを有する構造体として宣言される.(bool型は丸マークバーを通るかどうかを示します.)
  • メッシュボード全体を1およびfalseに初期化します.
  • kの位置を見つけ、位置を基準に右下隅全体のcheckをtrueに変更し、円を通る位置に変換します.
  • 条件
  • を取得する位置の上または左側がfalseである場合、これらのパスはいずれも円を通過していないパスであるため、numごとに加算され、checkはfalseとして保存される.
  • の上または左側のいずれかがtrueである場合、true部分のnumは、円を通る場所だけが得られる.
  • 上も左もtrueなら両方とも丸を通る経路なので、それぞれのnumを付けてcheckはtrueとして保存します.
  • 3回の条件が完了した後、要求された位置のcheck値がtrueであれば、その部分は円または円が通る経路であるため、無条件にtrueに変換される.(図中の赤色部分を処理する方法)

    • 最終出力dp[n][m].numでよい.

    [ソースコード]

    package main

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

type node struct {
	num   int
	check bool
}

var n, m, k int
var dp [16][16]node

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	fmt.Fscan(r, &n, &m, &k)

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			dp[i][j] = node{
				num:   1,
				check: false,
			}
		}
	}
	if k != 0 {
		k--
		x := k / m
		y := k % m
		for i := x + 1; i <= n; i++ {
			for j := y + 1; j <= m; j++ {
				dp[i][j].check = true
			}
		}

	}

	for i := 2; i <= n; i++ {
		for j := 2; j <= m; j++ {
			num1 := dp[i-1][j].num
			num2 := dp[i][j-1].num
			temp1 := dp[i-1][j].check
			temp2 := dp[i][j-1].check
			nextnum := num1 + num2
			nextcheck := true
			if temp1 == false && temp2 == false {
				nextcheck = false
			} else if temp1 && temp2 == false {
				nextnum = num1
			} else if temp1 == false && temp2 {
				nextnum = num2
			}

			if dp[i][j].check {
				nextcheck = true
			}

			dp[i][j] = node{
				num:   nextnum,
				check: nextcheck,
			}
		}
	}

	fmt.Fprintln(w, dp[n][m].num)
}
    disk buffer, cache, swap
    Packet capture on Firewalls (ASA/PIX/FWSM)