問題
下図のように、完全に水平な通りと垂直な筋からなる街路がある。
地点Aから地点Bへ行く最短経路は何通りあるか？
但し、灰色で示された通行止めの区域は通ってはならない。
方針
「最短経路の数え上げ」の問題と、基本的に全く同じです。
この問題では、動的計画法を使いました。
（i, j)点まで経路数をP(i, j)とすると
が成り立ちます。
今回のケースは、(2, 2)の地点に立ち入ることができません。
この為、第３の項目が加えます。
この問題では、動的計画法を使いました。
（i, j)点まで経路数をP(i, j)とすると
0 <
i <= m, 0 < j <= nの場合
|
P(i, j)
= P(i, j - 1) + P(i - 1, j)
|
i = 0またはj = 0の場合
|
P(i, j) = 1
|
が成り立ちます。
今回のケースは、(2, 2)の地点に立ち入ることができません。
この為、第３の項目が加えます。
0 <
i <= m, 0 < j <= nの場合
|
P(i, j)
= P(i, j - 1) + P(i - 1, j)
|
i = 0またはj = 0の場合
|
P(i, j) = 1
|
i = 2かつj = 2の場合
|
P(i, j)
= 0
|
これをコードにすると、以下のようになります。
コード
swift3
//
// BlockedPathsMatrix.swift
// BlockedPaths
//
// Created by shinichirou.yamazaki. on 2017/03/03.
// Copyright © 2017 shinichirou.yamazaki. All rights reserved.
//
import Foundation
class BlockedPathsMatrix
{
// 各ポイントへの最短経路数を
// m_cNum * m_rNumの２次元配列と考える
var m_elements: [[Int]] = []
var m_cNum = 0
var m_rNum = 0
// 初期化処理
init(rNum:Int, cNum:Int)
{
m_cNum = cNum
m_rNum = rNum
let row = Array(repeating: -1, count: m_cNum)
m_elements = Array(repeating: row, count: m_rNum)
}
// 各ポイントの計算処理//
// BlockedPathsMatrix.swift
// BlockedPaths
//
// Created by shinichirou.yamazaki. on 2017/03/03.
// Copyright © 2017 shinichirou.yamazaki. All rights reserved.
//
import Foundation
class BlockedPathsMatrix
{
// 各ポイントへの最短経路数を
// m_cNum * m_rNumの２次元配列と考える
var m_elements: [[Int]] = []
var m_cNum = 0
var m_rNum = 0
// 初期化処理
init(rNum:Int, cNum:Int)
{
m_cNum = cNum
m_rNum = rNum
let row = Array(repeating: -1, count: m_cNum)
m_elements = Array(repeating: row, count: m_rNum)
}
// 各ポイントの計算処理
func calculate()
{
for row in 0...(m_rNum - 1)
{
for col in 0...(m_cNum - 1)
{
if (col == 0 || row == 0)
{
m_elements[row][col] = 1
}
// 新たに加わった条件
else if (col == 2 && row == 2)
{
m_elements[row][col] = 0
}
else
{
m_elements[row][col] =
m_elements[row][col - 1] + m_elements[row - 1][col]
}
}
}
}
func printMatrix()
{
print(m_elements)
}
}
var matrix = BlockedPathsMatrix(rNum: 4, cNum: 5)
matrix.calculate()
matrix.printMatrix()
実行結果
[[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 0, 4, 9], [1, 4, 4, 8, 17]]
マトリックス上では以下のようになります。
