WindowsのdiffコマンドをC#でささっと作る

<font color=gray>ふつうの人は WinMerge を使いましょう。</font>

# 0. はじめに

Windows 付属の FC コマンドの出来が酷いのだ。UNIX などで用いられる diff コマンドと比べると，大規模なテキストにおける差分抽出能力がとても低いように思える。

# 1. 仕様案（お品書き）

- 比較アルゴリズムは UNIX の `diff` コマンド準拠とする。
- 比較結果の出力について，Windows 付属の `FC` コマンドの出力形式に準拠する。
- 文字コードについて，ファイルの先頭に BOM（バイト順マーク）があれば従うが，無い場合はシステムデフォルト値（日本語版 Windows の場合は Shift-JIS）に従う。
- オプション `/N` を指定すると行番号を表示する。行番号は5桁表示とする。
- ファイルが一致する場合の返値は 0，不一致の場合は 1，エラーの場合は -1 を返す。
  ※Windows 付属の `FC` コマンドではエラーの場合も 1 を返す。
- 使用言語は C# とする。Windows 10 付属の C# コンパイラでビルドできること。

# 2. UNIX の diff コマンドのアルゴリズムについて

UNIX の `diff` コマンドのアルゴリズムについては古くから論文が出ており，詳しくは参考文献を参照して欲しい。 このうち最も基礎的と思われる動的計画法を用いたアルゴリズムを自分なりに咀嚼した内容を以下記す。

## 2.1 サンプルファイル

本記事で取り扱う変更前後のサンプルファイルを以下に示す。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="200" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h168 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">変更前 SAMPLE1.TXT</text>
</svg>
title
<$TITLE>

<code>
Ａ
Ｂ
Ｃ
Ｄ
Ｅ
Ｆ
Ｇ
Ｈ
Ｉ
Ｊ
Ｋ
Ｌ
</code>
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="200" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h168 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">変更後 SAMPLE2.TXT</text>
</svg>
title
<$TITLE>

<code>
Ａ
Ｂ
Ｅ
Ｆ
Ａ
Ｂ
Ｇ
Ｈ
Ｃ
Ｄ
Ｋ
Ｌ
</code>
end title
@enduml
```

## 2.2 照合マップ

まず，変更前の $i$ 行と変更後の $j$ 行を比較した結果である照合マップ $C(i,j)$ を作成する。二つの行が一致していれば $C(i,j) = 1$ とし `◯` で示す。一方，不一致の場合 $C(i,j) = 0$ として空白で示す。なお <font color=lightblue>■</font> で示す余白部分の意味については後述する。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontSize 16
  fontStyle normal
}
</style>
sprite FIGURE <svg width="544" height="544">
<g fill="lightblue">
<path d="M80 80 h416 v32 h-416">
<path d="M80 80 v416 h32 v-416">
</g>
<g fill="lightgray">
<path d="M112 112 h32 v32 h-32">
<path d="M144 144 h32 v32 h-32">
<path d="M176 240 h32 v32 h-32">
<path d="M208 272 h32 v32 h-32">
<path d="M240 112 h32 v32 h-32">
<path d="M272 144 h32 v32 h-32">
<path d="M304 304 h32 v32 h-32">
<path d="M336 336 h32 v32 h-32">
<path d="M368 176 h32 v32 h-32">
<path d="M400 208 h32 v32 h-32">
<path d="M432 432 h32 v32 h-32">
<path d="M464 464 h32 v32 h-32">
</g>
<g fill="black">
<path d="M16 16  h480 v1 h-480">
<path d="M80 48  h416 v1 h-416">
<path d="M16 80  h480 v1 h-480">
<path d="M48 112 h448 v1 h-448">
<path d="M48 144 h448 v1 h-448">
<path d="M48 176 h448 v1 h-448">
<path d="M48 208 h448 v1 h-448">
<path d="M48 240 h448 v1 h-448">
<path d="M48 272 h448 v1 h-448">
<path d="M48 304 h448 v1 h-448">
<path d="M48 336 h448 v1 h-448">
<path d="M48 368 h448 v1 h-448">
<path d="M48 400 h448 v1 h-448">
<path d="M48 432 h448 v1 h-448">
<path d="M48 464 h448 v1 h-448">
<path d="M16 496 h480 v1 h-480">
<path d="M16  16 v480 h1 v-480">
<path d="M48  80 v416 h1 v-416">
<path d="M80  16 v480 h1 v-480">
<path d="M112 48 v448 h1 v-448">
<path d="M144 48 v448 h1 v-448">
<path d="M176 48 v448 h1 v-448">
<path d="M208 48 v448 h1 v-448">
<path d="M240 48 v448 h1 v-448">
<path d="M272 48 v448 h1 v-448">
<path d="M304 48 v448 h1 v-448">
<path d="M336 48 v448 h1 v-448">
<path d="M368 48 v448 h1 v-448">
<path d="M400 48 v448 h1 v-448">
<path d="M432 48 v448 h1 v-448">
<path d="M464 48 v448 h1 v-448">
<path d="M496 16 v480 h1 v-480">
</g>
<text x="252" y="42" fill="black" font-size="20">変 更 後</text>
<text x="118" y="74" fill="black" font-size="20">Ａ</text>
<text x="150" y="74" fill="black" font-size="20">Ｂ</text>
<text x="182" y="74" fill="black" font-size="20">Ｅ</text>
<text x="214" y="74" fill="black" font-size="20">Ｆ</text>
<text x="246" y="74" fill="black" font-size="20">Ａ</text>
<text x="278" y="74" fill="black" font-size="20">Ｂ</text>
<text x="310" y="74" fill="black" font-size="20">Ｇ</text>
<text x="342" y="74" fill="black" font-size="20">Ｈ</text>
<text x="374" y="74" fill="black" font-size="20">Ｃ</text>
<text x="406" y="74" fill="black" font-size="20">Ｄ</text>
<text x="438" y="74" fill="black" font-size="20">Ｋ</text>
<text x="470" y="74" fill="black" font-size="20">Ｌ</text>
<text x="22" y="272" fill="black" font-size="20">変</text>
<text x="22" y="298" fill="black" font-size="20">更</text>
<text x="22" y="324" fill="black" font-size="20">前</text>
<text x="54" y="138" fill="black" font-size="20">Ａ</text>
<text x="54" y="170" fill="black" font-size="20">Ｂ</text>
<text x="54" y="202" fill="black" font-size="20">Ｃ</text>
<text x="54" y="234" fill="black" font-size="20">Ｄ</text>
<text x="54" y="266" fill="black" font-size="20">Ｅ</text>
<text x="54" y="298" fill="black" font-size="20">Ｆ</text>
<text x="54" y="330" fill="black" font-size="20">Ｇ</text>
<text x="54" y="362" fill="black" font-size="20">Ｈ</text>
<text x="54" y="394" fill="black" font-size="20">Ｉ</text>
<text x="54" y="426" fill="black" font-size="20">Ｊ</text>
<text x="54" y="458" fill="black" font-size="20">Ｋ</text>
<text x="54" y="490" fill="black" font-size="20">Ｌ</text>
<g fill="none" stroke="black">
<circle cx="128" cy="128" r="8">
<circle cx="160" cy="160" r="8">
<circle cx="192" cy="256" r="8">
<circle cx="224" cy="288" r="8">
<circle cx="256" cy="128" r="8">
<circle cx="288" cy="160" r="8">
<circle cx="320" cy="320" r="8">
<circle cx="352" cy="354" r="8">
<circle cx="384" cy="192" r="8">
<circle cx="416" cy="224" r="8">
<circle cx="448" cy="448" r="8">
<circle cx="480" cy="480" r="8">
</g>
<text x="56" y="526" fill="black" font-size="16">ｉ</text>
<text x="510" y="72" fill="black" font-size="16">ｊ</text>
<path d="M506 80 h15 v-3 l15 4 l-15 4 v-3 h-15" fill="black">
<path d="M80 508 v15 h-3 l 4 15 l4 -15 h-3 v-15" fill="black">
</svg>
title
<$FIGURE>
図１　照合マップ <math>C(i,j)</math>
end title
@enduml
```

ここで左上端のマス（始点）から右下端のマス（終点）まで，できるだけ多くの一致するマス `◯` を通過する経路（最短経路）を求めてやればよい。原則としてマスを右または下に一つずつしか移動できないものとし，二つの行が一致しているマスのみ斜め移動可能とする。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontSize 16
  fontStyle normal
}
</style>
sprite FIGURE <svg width="544" height="544">
<g fill="lightblue">
<path d="M80 80 h416 v32 h-416">
<path d="M80 80 v416 h32 v-416">
</g>
<g fill="lightgray">
<path d="M112 112 h32 v32 h-32">
<path d="M144 144 h32 v32 h-32">
<path d="M176 240 h32 v32 h-32">
<path d="M208 272 h32 v32 h-32">
<path d="M240 112 h32 v32 h-32">
<path d="M272 144 h32 v32 h-32">
<path d="M304 304 h32 v32 h-32">
<path d="M336 336 h32 v32 h-32">
<path d="M368 176 h32 v32 h-32">
<path d="M400 208 h32 v32 h-32">
<path d="M432 432 h32 v32 h-32">
<path d="M464 464 h32 v32 h-32">
</g>
<g fill="yellow">
<path d="M144 176 h32 v32 h-32">
<path d="M144 208 h32 v32 h-32">
<path d="M240 272 h32 v32 h-32">
<path d="M272 272 h32 v32 h-32">
<path d="M336 368 h32 v32 h-32">
<path d="M336 400 h32 v32 h-32">
<path d="M368 400 h32 v32 h-32">
<path d="M400 400 h32 v32 h-32">
</g>
<g fill="black">
<path d="M16 16  h480 v1 h-480">
<path d="M80 48  h416 v1 h-416">
<path d="M16 80  h480 v1 h-480">
<path d="M48 112 h448 v1 h-448">
<path d="M48 144 h448 v1 h-448">
<path d="M48 176 h448 v1 h-448">
<path d="M48 208 h448 v1 h-448">
<path d="M48 240 h448 v1 h-448">
<path d="M48 272 h448 v1 h-448">
<path d="M48 304 h448 v1 h-448">
<path d="M48 336 h448 v1 h-448">
<path d="M48 368 h448 v1 h-448">
<path d="M48 400 h448 v1 h-448">
<path d="M48 432 h448 v1 h-448">
<path d="M48 464 h448 v1 h-448">
<path d="M16 496 h480 v1 h-480">
<path d="M16  16 v480 h1 v-480">
<path d="M48  80 v416 h1 v-416">
<path d="M80  16 v480 h1 v-480">
<path d="M112 48 v448 h1 v-448">
<path d="M144 48 v448 h1 v-448">
<path d="M176 48 v448 h1 v-448">
<path d="M208 48 v448 h1 v-448">
<path d="M240 48 v448 h1 v-448">
<path d="M272 48 v448 h1 v-448">
<path d="M304 48 v448 h1 v-448">
<path d="M336 48 v448 h1 v-448">
<path d="M368 48 v448 h1 v-448">
<path d="M400 48 v448 h1 v-448">
<path d="M432 48 v448 h1 v-448">
<path d="M464 48 v448 h1 v-448">
<path d="M496 16 v480 h1 v-480">
</g>
<text x="252" y="42" fill="black" font-size="20">変 更 後</text>
<text x="118" y="74" fill="black" font-size="20">Ａ</text>
<text x="150" y="74" fill="black" font-size="20">Ｂ</text>
<text x="182" y="74" fill="black" font-size="20">Ｅ</text>
<text x="214" y="74" fill="black" font-size="20">Ｆ</text>
<text x="246" y="74" fill="black" font-size="20">Ａ</text>
<text x="278" y="74" fill="black" font-size="20">Ｂ</text>
<text x="310" y="74" fill="black" font-size="20">Ｇ</text>
<text x="342" y="74" fill="black" font-size="20">Ｈ</text>
<text x="374" y="74" fill="black" font-size="20">Ｃ</text>
<text x="406" y="74" fill="black" font-size="20">Ｄ</text>
<text x="438" y="74" fill="black" font-size="20">Ｋ</text>
<text x="470" y="74" fill="black" font-size="20">Ｌ</text>
<text x="22" y="272" fill="black" font-size="20">変</text>
<text x="22" y="298" fill="black" font-size="20">更</text>
<text x="22" y="324" fill="black" font-size="20">前</text>
<text x="54" y="138" fill="black" font-size="20">Ａ</text>
<text x="54" y="170" fill="black" font-size="20">Ｂ</text>
<text x="54" y="202" fill="black" font-size="20">Ｃ</text>
<text x="54" y="234" fill="black" font-size="20">Ｄ</text>
<text x="54" y="266" fill="black" font-size="20">Ｅ</text>
<text x="54" y="298" fill="black" font-size="20">Ｆ</text>
<text x="54" y="330" fill="black" font-size="20">Ｇ</text>
<text x="54" y="362" fill="black" font-size="20">Ｈ</text>
<text x="54" y="394" fill="black" font-size="20">Ｉ</text>
<text x="54" y="426" fill="black" font-size="20">Ｊ</text>
<text x="54" y="458" fill="black" font-size="20">Ｋ</text>
<text x="54" y="490" fill="black" font-size="20">Ｌ</text>
<g fill="none" stroke="black">
<circle cx="128" cy="128" r="8">
<circle cx="160" cy="160" r="8">
<circle cx="192" cy="256" r="8">
<circle cx="224" cy="288" r="8">
<circle cx="256" cy="128" r="8">
<circle cx="288" cy="160" r="8">
<circle cx="320" cy="320" r="8">
<circle cx="352" cy="354" r="8">
<circle cx="384" cy="192" r="8">
<circle cx="416" cy="224" r="8">
<circle cx="448" cy="448" r="8">
<circle cx="480" cy="480" r="8">
</g>
<text x="56" y="526" fill="black" font-size="16">ｉ</text>
<text x="510" y="72" fill="black" font-size="16">ｊ</text>
<path d="M506 80 h15 v-3 l15 4 l-15 4 v-3 h-15" fill="black">
<path d="M80 508 v15 h-3 l 4 15 l4 -15 h-3 v-15" fill="black">
<g fill="red">
<path d="M100  94  h71.5 v-3 l15 5 l-15 5 v-3 h-71.5" transform="rotate(45,96,96)"/>
<path d="M158 163 v47 h-3 l5 15 l5 -15 h-3 v-47">
<path d="M164 222 h71.5 v-3 l15 5 l-15 5 v-3 h-71.5" transform="rotate(45,160,224)"/>
<path d="M227 286 h47 v-3 l15 5 l-15 5 v-3 h-47">
<path d="M292 286 h71.5 v-3 l15 5 l-15 5 v-3 h-71.5" transform="rotate(45,288,288)"/>
<path d="M350 354 v47 h-3 l5 15 l5 -15 h-3 v-47">
<path d="M356 414 h47 v-3 l15 5 l-15 5 v-3 h-47">
<path d="M420 414 h71.5 v-3 l15 5 l-15 5 v-3 h-71.5" transform="rotate(45,416,416)"/>
</g>
</svg>
title
<$FIGURE>
図２　始点から終点までの最短経路
end title
@enduml
```

:::note
変更前後で内容が一致している部分は斜めに移動，削除された部分は下方向に移動，追加された部分は右方向に移動する。変更された部分は下方向への移動と右方向への移動の組み合わせである。
:::

## 2.3 距離マップ

このような最短経路を求めるため，まず始点から各マスへの距離マップ $D(i,j)$ を求める。

- 各マスの距離 $D(i,j)$ は左および上のマスの距離を参照するため，参照エラーが生じないよう余白部分 <font color=lightblue>■</font> を設け，$D(i,0) = i$，$D(0,j) = j$ とする。
- マスが一致しない場合，すなわち $C(i,j) = 0$ のとき，左のマスの距離に１を加えたものと上のマスの距離に１を加えたもののうち小さいほうとする。
  ```math
  D(i,j) = \min \left\{ \,\, D(i - 1, j) + 1,\,\, D(i, j - 1) + 1 \,\, \right\}
  ```
- マスが一致している場合，すなわち $C(i,j) = 1$ のとき，さらに左上のマスの距離との最小値とする。
  ```math
  D(i,j) = \min \left\{ \,\, D(i - 1, j) + 1,\,\, D(i, j - 1) + 1 ,\,\, D(i- 1,j - 1) \,\, \right\}
  ```

このようにして求めた距離マップ $D(i,j)$ を以下に示す。※一致するマスは <font color=lightgray>■</font> で示す。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontSize 16
  fontStyle normal
}
</style>
sprite FIGURE <svg width="544" height="544">
<g fill="lightblue">
<path d="M80 80 h416 v32 h-416">
<path d="M80 80 v416 h32 v-416">
</g>
<g fill="lightgray">
<path d="M112 112 h32 v32 h-32">
<path d="M144 144 h32 v32 h-32">
<path d="M176 240 h32 v32 h-32">
<path d="M208 272 h32 v32 h-32">
<path d="M240 112 h32 v32 h-32">
<path d="M272 144 h32 v32 h-32">
<path d="M304 304 h32 v32 h-32">
<path d="M336 336 h32 v32 h-32">
<path d="M368 176 h32 v32 h-32">
<path d="M400 208 h32 v32 h-32">
<path d="M432 432 h32 v32 h-32">
<path d="M464 464 h32 v32 h-32">
</g>
<g fill="black">
<path d="M16 16  h480 v1 h-480">
<path d="M80 48  h416 v1 h-416">
<path d="M16 80  h480 v1 h-480">
<path d="M48 112 h448 v1 h-448">
<path d="M48 144 h448 v1 h-448">
<path d="M48 176 h448 v1 h-448">
<path d="M48 208 h448 v1 h-448">
<path d="M48 240 h448 v1 h-448">
<path d="M48 272 h448 v1 h-448">
<path d="M48 304 h448 v1 h-448">
<path d="M48 336 h448 v1 h-448">
<path d="M48 368 h448 v1 h-448">
<path d="M48 400 h448 v1 h-448">
<path d="M48 432 h448 v1 h-448">
<path d="M48 464 h448 v1 h-448">
<path d="M16 496 h480 v1 h-480">
<path d="M16  16 v480 h1 v-480">
<path d="M48  80 v416 h1 v-416">
<path d="M80  16 v480 h1 v-480">
<path d="M112 48 v448 h1 v-448">
<path d="M144 48 v448 h1 v-448">
<path d="M176 48 v448 h1 v-448">
<path d="M208 48 v448 h1 v-448">
<path d="M240 48 v448 h1 v-448">
<path d="M272 48 v448 h1 v-448">
<path d="M304 48 v448 h1 v-448">
<path d="M336 48 v448 h1 v-448">
<path d="M368 48 v448 h1 v-448">
<path d="M400 48 v448 h1 v-448">
<path d="M432 48 v448 h1 v-448">
<path d="M464 48 v448 h1 v-448">
<path d="M496 16 v480 h1 v-480">
</g>
<text x="252" y="42" fill="black" font-size="20">変 更 後</text>
<text x="118" y="74" fill="black" font-size="20">Ａ</text>
<text x="150" y="74" fill="black" font-size="20">Ｂ</text>
<text x="182" y="74" fill="black" font-size="20">Ｅ</text>
<text x="214" y="74" fill="black" font-size="20">Ｆ</text>
<text x="246" y="74" fill="black" font-size="20">Ａ</text>
<text x="278" y="74" fill="black" font-size="20">Ｂ</text>
<text x="310" y="74" fill="black" font-size="20">Ｇ</text>
<text x="342" y="74" fill="black" font-size="20">Ｈ</text>
<text x="374" y="74" fill="black" font-size="20">Ｃ</text>
<text x="406" y="74" fill="black" font-size="20">Ｄ</text>
<text x="438" y="74" fill="black" font-size="20">Ｋ</text>
<text x="470" y="74" fill="black" font-size="20">Ｌ</text>
<text x="22" y="272" fill="black" font-size="20">変</text>
<text x="22" y="298" fill="black" font-size="20">更</text>
<text x="22" y="324" fill="black" font-size="20">前</text>
<text x="54" y="138" fill="black" font-size="20">Ａ</text>
<text x="54" y="170" fill="black" font-size="20">Ｂ</text>
<text x="54" y="202" fill="black" font-size="20">Ｃ</text>
<text x="54" y="234" fill="black" font-size="20">Ｄ</text>
<text x="54" y="266" fill="black" font-size="20">Ｅ</text>
<text x="54" y="298" fill="black" font-size="20">Ｆ</text>
<text x="54" y="330" fill="black" font-size="20">Ｇ</text>
<text x="54" y="362" fill="black" font-size="20">Ｈ</text>
<text x="54" y="394" fill="black" font-size="20">Ｉ</text>
<text x="54" y="426" fill="black" font-size="20">Ｊ</text>
<text x="54" y="458" fill="black" font-size="20">Ｋ</text>
<text x="54" y="490" fill="black" font-size="20">Ｌ</text>

<text x="92"  y="104" fill="black" font-size="16">0</text>
<text x="124" y="104" fill="black" font-size="16">1</text>
<text x="156" y="104" fill="black" font-size="16">2</text>
<text x="188" y="104" fill="black" font-size="16">3</text>
<text x="220" y="104" fill="black" font-size="16">4</text>
<text x="252" y="104" fill="black" font-size="16">5</text>
<text x="284" y="104" fill="black" font-size="16">6</text>
<text x="316" y="104" fill="black" font-size="16">7</text>
<text x="348" y="104" fill="black" font-size="16">8</text>
<text x="380" y="104" fill="black" font-size="16">9</text>
<text x="406" y="104" fill="black" font-size="16">10</text>
<text x="438" y="104" fill="black" font-size="16">11</text>
<text x="470" y="104" fill="black" font-size="16">12</text>

<text x="92"  y="136" fill="black" font-size="16">1</text>
<text x="124" y="136" fill="black" font-size="16">0</text>
<text x="156" y="136" fill="black" font-size="16">1</text>
<text x="188" y="136" fill="black" font-size="16">2</text>
<text x="220" y="136" fill="black" font-size="16">3</text>
<text x="252" y="136" fill="black" font-size="16">4</text>
<text x="284" y="136" fill="black" font-size="16">5</text>
<text x="316" y="136" fill="black" font-size="16">6</text>
<text x="348" y="136" fill="black" font-size="16">7</text>
<text x="380" y="136" fill="black" font-size="16">8</text>
<text x="412" y="136" fill="black" font-size="16">9</text>
<text x="438" y="136" fill="black" font-size="16">10</text>
<text x="470" y="136" fill="black" font-size="16">11</text>

<text x="92"  y="168" fill="black" font-size="16">2</text>
<text x="124" y="168" fill="black" font-size="16">1</text>
<text x="156" y="168" fill="black" font-size="16">0</text>
<text x="188" y="168" fill="black" font-size="16">1</text>
<text x="220" y="168" fill="black" font-size="16">2</text>
<text x="252" y="168" fill="black" font-size="16">3</text>
<text x="284" y="168" fill="black" font-size="16">4</text>
<text x="316" y="168" fill="black" font-size="16">5</text>
<text x="348" y="168" fill="black" font-size="16">6</text>
<text x="380" y="168" fill="black" font-size="16">7</text>
<text x="412" y="168" fill="black" font-size="16">8</text>
<text x="444" y="168" fill="black" font-size="16">9</text>
<text x="470" y="168" fill="black" font-size="16">10</text>

<text x="92"  y="200" fill="black" font-size="16">3</text>
<text x="124" y="200" fill="black" font-size="16">2</text>
<text x="156" y="200" fill="black" font-size="16">1</text>
<text x="188" y="200" fill="black" font-size="16">2</text>
<text x="220" y="200" fill="black" font-size="16">3</text>
<text x="252" y="200" fill="black" font-size="16">4</text>
<text x="284" y="200" fill="black" font-size="16">5</text>
<text x="316" y="200" fill="black" font-size="16">6</text>
<text x="348" y="200" fill="black" font-size="16">7</text>
<text x="380" y="200" fill="black" font-size="16">6</text>
<text x="412" y="200" fill="black" font-size="16">7</text>
<text x="444" y="200" fill="black" font-size="16">8</text>
<text x="476" y="200" fill="black" font-size="16">9</text>

<text x="92"  y="232" fill="black" font-size="16">4</text>
<text x="124" y="232" fill="black" font-size="16">3</text>
<text x="156" y="232" fill="black" font-size="16">2</text>
<text x="188" y="232" fill="black" font-size="16">3</text>
<text x="220" y="232" fill="black" font-size="16">4</text>
<text x="252" y="232" fill="black" font-size="16">5</text>
<text x="284" y="232" fill="black" font-size="16">6</text>
<text x="316" y="232" fill="black" font-size="16">7</text>
<text x="348" y="232" fill="black" font-size="16">8</text>
<text x="380" y="232" fill="black" font-size="16">7</text>
<text x="412" y="232" fill="black" font-size="16">6</text>
<text x="444" y="232" fill="black" font-size="16">7</text>
<text x="476" y="232" fill="black" font-size="16">8</text>

<text x="92"  y="264" fill="black" font-size="16">5</text>
<text x="124" y="264" fill="black" font-size="16">4</text>
<text x="156" y="264" fill="black" font-size="16">3</text>
<text x="188" y="264" fill="black" font-size="16">2</text>
<text x="220" y="264" fill="black" font-size="16">3</text>
<text x="252" y="264" fill="black" font-size="16">4</text>
<text x="284" y="264" fill="black" font-size="16">5</text>
<text x="316" y="264" fill="black" font-size="16">6</text>
<text x="348" y="264" fill="black" font-size="16">7</text>
<text x="380" y="264" fill="black" font-size="16">8</text>
<text x="412" y="264" fill="black" font-size="16">7</text>
<text x="444" y="264" fill="black" font-size="16">8</text>
<text x="476" y="264" fill="black" font-size="16">9</text>

<text x="92"  y="296" fill="black" font-size="16">6</text>
<text x="124" y="296" fill="black" font-size="16">5</text>
<text x="156" y="296" fill="black" font-size="16">4</text>
<text x="188" y="296" fill="black" font-size="16">3</text>
<text x="220" y="296" fill="black" font-size="16">2</text>
<text x="252" y="296" fill="black" font-size="16">3</text>
<text x="284" y="296" fill="black" font-size="16">4</text>
<text x="316" y="296" fill="black" font-size="16">5</text>
<text x="348" y="296" fill="black" font-size="16">6</text>
<text x="380" y="296" fill="black" font-size="16">7</text>
<text x="412" y="296" fill="black" font-size="16">8</text>
<text x="444" y="296" fill="black" font-size="16">9</text>
<text x="470" y="296" fill="black" font-size="16">10</text>

<text x="92"  y="328" fill="black" font-size="16">7</text>
<text x="124" y="328" fill="black" font-size="16">6</text>
<text x="156" y="328" fill="black" font-size="16">5</text>
<text x="188" y="328" fill="black" font-size="16">4</text>
<text x="220" y="328" fill="black" font-size="16">3</text>
<text x="252" y="328" fill="black" font-size="16">4</text>
<text x="284" y="328" fill="black" font-size="16">5</text>
<text x="316" y="328" fill="black" font-size="16">4</text>
<text x="348" y="328" fill="black" font-size="16">5</text>
<text x="380" y="328" fill="black" font-size="16">6</text>
<text x="412" y="328" fill="black" font-size="16">7</text>
<text x="444" y="328" fill="black" font-size="16">8</text>
<text x="476" y="328" fill="black" font-size="16">9</text>

<text x="92"  y="360" fill="black" font-size="16">8</text>
<text x="124" y="360" fill="black" font-size="16">7</text>
<text x="156" y="360" fill="black" font-size="16">6</text>
<text x="188" y="360" fill="black" font-size="16">5</text>
<text x="220" y="360" fill="black" font-size="16">4</text>
<text x="252" y="360" fill="black" font-size="16">5</text>
<text x="284" y="360" fill="black" font-size="16">6</text>
<text x="316" y="360" fill="black" font-size="16">5</text>
<text x="348" y="360" fill="black" font-size="16">4</text>
<text x="380" y="360" fill="black" font-size="16">5</text>
<text x="412" y="360" fill="black" font-size="16">6</text>
<text x="444" y="360" fill="black" font-size="16">7</text>
<text x="476" y="360" fill="black" font-size="16">8</text>

<text x="92"  y="392" fill="black" font-size="16">9</text>
<text x="124" y="392" fill="black" font-size="16">8</text>
<text x="156" y="392" fill="black" font-size="16">7</text>
<text x="188" y="392" fill="black" font-size="16">6</text>
<text x="220" y="392" fill="black" font-size="16">5</text>
<text x="252" y="392" fill="black" font-size="16">6</text>
<text x="284" y="392" fill="black" font-size="16">7</text>
<text x="316" y="392" fill="black" font-size="16">6</text>
<text x="348" y="392" fill="black" font-size="16">5</text>
<text x="380" y="392" fill="black" font-size="16">6</text>
<text x="412" y="392" fill="black" font-size="16">7</text>
<text x="444" y="392" fill="black" font-size="16">8</text>
<text x="476" y="392" fill="black" font-size="16">9</text>

<text x="86"  y="424" fill="black" font-size="16">10</text>
<text x="124" y="424" fill="black" font-size="16">9</text>
<text x="156" y="424" fill="black" font-size="16">8</text>
<text x="188" y="424" fill="black" font-size="16">7</text>
<text x="220" y="424" fill="black" font-size="16">6</text>
<text x="252" y="424" fill="black" font-size="16">7</text>
<text x="284" y="424" fill="black" font-size="16">8</text>
<text x="316" y="424" fill="black" font-size="16">7</text>
<text x="348" y="424" fill="black" font-size="16">6</text>
<text x="380" y="424" fill="black" font-size="16">7</text>
<text x="412" y="424" fill="black" font-size="16">8</text>
<text x="444" y="424" fill="black" font-size="16">9</text>
<text x="470" y="424" fill="black" font-size="16">10</text>

<text x="86"  y="456" fill="black" font-size="16">11</text>
<text x="118" y="456" fill="black" font-size="16">10</text>
<text x="156" y="456" fill="black" font-size="16">9</text>
<text x="188" y="456" fill="black" font-size="16">8</text>
<text x="220" y="456" fill="black" font-size="16">7</text>
<text x="252" y="456" fill="black" font-size="16">8</text>
<text x="284" y="456" fill="black" font-size="16">9</text>
<text x="316" y="456" fill="black" font-size="16">8</text>
<text x="348" y="456" fill="black" font-size="16">7</text>
<text x="380" y="456" fill="black" font-size="16">8</text>
<text x="412" y="456" fill="black" font-size="16">9</text>
<text x="444" y="456" fill="black" font-size="16">8</text>
<text x="476" y="456" fill="black" font-size="16">9</text>

<text x="86"  y="488" fill="black" font-size="16">12</text>
<text x="118" y="488" fill="black" font-size="16">11</text>
<text x="150" y="488" fill="black" font-size="16">10</text>
<text x="188" y="488" fill="black" font-size="16">9</text>
<text x="220" y="488" fill="black" font-size="16">8</text>
<text x="252" y="488" fill="black" font-size="16">9</text>
<text x="278" y="488" fill="black" font-size="16">10</text>
<text x="316" y="488" fill="black" font-size="16">9</text>
<text x="348" y="488" fill="black" font-size="16">8</text>
<text x="380" y="488" fill="black" font-size="16">9</text>
<text x="406" y="488" fill="black" font-size="16">10</text>
<text x="444" y="488" fill="black" font-size="16">9</text>
<text x="476" y="488" fill="black" font-size="16">8</text>

<text x="56" y="526" fill="black" font-size="16">ｉ</text>
<text x="510" y="72" fill="black" font-size="16">ｊ</text>
<path d="M506 80 h15 v-3 l15 4 l-15 4 v-3 h-15" fill="black">
<path d="M80 508 v15 h-3 l 4 15 l4 -15 h-3 v-15" fill="black">
</svg>
title
<$FIGURE>
図３　始点からの距離マップ <math>D(i,j)</math>
end title
@endum
```

## 2.4 最短経路

始点からの最短経路は，終点から逆算して求める。

### (1) 斜め移動の条件

$i \ge 1$，$j \ge 1$，$C(i,j) = 1$，$D(i-1,j-1) \le D(i-1,j)$，$D(i-1,j-1) \le D(i,j-1)$ のとき

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontSize 16
  fontStyle normal
}
</style>
sprite FIGURE <svg width="256" height="256">
<path d="M128 128 h64 v64 h-64" fill="lightgray">
<g fill="black">
<path d="M32 64  h192 v1 h-192">
<path d="M32 128 h192 v1 h-192">
<path d="M32 192 h192 v1 h-192">
<path d="M64  32 v192 h1 v-192">
<path d="M128 32 v192 h1 v-192">
<path d="M192 32 v192 h1 v-192">
</g>
<path d="M100 97 l30 -10 v6 h50.5 v8 h-50.5 v6" fill="pink" transform="rotate(45,96,96)">
<text x="148" y="168" fill="black" font-size="16">(i,j)</text>
<text x="140" y="104" fill="black" font-size="16">(i-1,j)</text>
<text x="78"  y="168" fill="black" font-size="16">(i,j-1)</text>
<text x="70"  y="104" fill="black" font-size="16">(i-1,j-1)</text>
</svg>
title
<$FIGURE>
図４－１　斜めに移動
end title
@enduml
```

### (2) 左に移動の条件

$j \ge 1$，$C(i,j) = 1$，$D(i, j - 1) \le D(i - 1, j)$，$D(i, j - 1) < D(i - 1, j - 1)$ のとき
$j \ge 1$，$C(i,j) = 0$，$D(i, j - 1) \le D(i - 1, j)$ のとき

```plantuml
@startuml
<style>
root {
  margin: 0;
  padding: 0;
}
title {
  fontSize: 16;
  fontStyle: normal;
}
</style>
sprite FIGURE <svg width="256" height="256">
<path d="M128 128 h64 v64 h-64" fill="yellow">
<g fill="black">
<path d="M32 64  h192 v1 h-192">
<path d="M32 128 h192 v1 h-192">
<path d="M32 192 h192 v1 h-192">
<path d="M64  32 v192 h1 v-192">
<path d="M128 32 v192 h1 v-192">
<path d="M192 32 v192 h1 v-192">
</g>
<path d="M100 160 l30 -10 v6 h24 v8 h-24 v6" fill="pink">
<text x="148" y="168" fill="black" font-size="16">(i,j)</text>
<text x="140" y="104" fill="black" font-size="16">(i-1,j)</text>
<text x="78"  y="168" fill="black" font-size="16">(i,j-1)</text>
<text x="70"  y="104" fill="black" font-size="16">(i-1,j-1)</text>
</svg>
title
<$FIGURE>
図４－２　左に移動
end title
@enduml
```

### (3) 上に移動する条件

$i \ge 1$，$C(i,j) = 1$，$D(i - 1, j) < D(i, j - 1)$，$D(i - 1, j) < D(i - 1, j - 1)$ のとき
$i \ge 1$，$C(i,j) = 0$，$D(i - 1, j) < D(i, j - 1)$ のとき

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontSize 16
  fontStyle normal
}
</style>
sprite FIGURE <svg width="256" height="256">
<path d="M128 128 h64 v64 h-64" fill="yellow">
<g fill="black">
<path d="M32 64  h192 v1 h-192">
<path d="M32 128 h192 v1 h-192">
<path d="M32 192 h192 v1 h-192">
<path d="M64  32 v192 h1 v-192">
<path d="M128 32 v192 h1 v-192">
<path d="M192 32 v192 h1 v-192">
</g>
<path d="M160 100 l10 30 h-6 v24 h-8 v-24 h-6" fill="pink">
<text x="148" y="168" fill="black" font-size="16">(i,j)</text>
<text x="140" y="104" fill="black" font-size="16">(i-1,j)</text>
<text x="78"  y="168" fill="black" font-size="16">(i,j-1)</text>
<text x="70"  y="104" fill="black" font-size="16">(i-1,j-1)</text>
</svg>
title
<$FIGURE>
図４－３　上に移動
end title
@enduml
```

以上のルールに基づいて，終点から始点まで最短経路を辿ると下記のようになる。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontSize 16
  fontStyle normal
}
</style>
sprite FIGURE <svg width="544" height="544">
<g fill="lightblue">
<path d="M80 80 h416 v32 h-416">
<path d="M80 80 v416 h32 v-416">
</g>
<g fill="lightgray">
<path d="M112 112 h32 v32 h-32">
<path d="M144 144 h32 v32 h-32">
<path d="M176 240 h32 v32 h-32">
<path d="M208 272 h32 v32 h-32">
<path d="M240 112 h32 v32 h-32">
<path d="M272 144 h32 v32 h-32">
<path d="M304 304 h32 v32 h-32">
<path d="M336 336 h32 v32 h-32">
<path d="M368 176 h32 v32 h-32">
<path d="M400 208 h32 v32 h-32">
<path d="M432 432 h32 v32 h-32">
<path d="M464 464 h32 v32 h-32">
</g>
<g fill="yellow">
<path d="M144 176 h32 v32 h-32">
<path d="M144 208 h32 v32 h-32">
<path d="M240 272 h32 v32 h-32">
<path d="M272 272 h32 v32 h-32">
<path d="M336 368 h32 v32 h-32">
<path d="M336 400 h32 v32 h-32">
<path d="M368 400 h32 v32 h-32">
<path d="M400 400 h32 v32 h-32">
</g>
<g fill="black">
<path d="M16 16  h480 v1 h-480">
<path d="M80 48  h416 v1 h-416">
<path d="M16 80  h480 v1 h-480">
<path d="M48 112 h448 v1 h-448">
<path d="M48 144 h448 v1 h-448">
<path d="M48 176 h448 v1 h-448">
<path d="M48 208 h448 v1 h-448">
<path d="M48 240 h448 v1 h-448">
<path d="M48 272 h448 v1 h-448">
<path d="M48 304 h448 v1 h-448">
<path d="M48 336 h448 v1 h-448">
<path d="M48 368 h448 v1 h-448">
<path d="M48 400 h448 v1 h-448">
<path d="M48 432 h448 v1 h-448">
<path d="M48 464 h448 v1 h-448">
<path d="M16 496 h480 v1 h-480">
<path d="M16  16 v480 h1 v-480">
<path d="M48  80 v416 h1 v-416">
<path d="M80  16 v480 h1 v-480">
<path d="M112 48 v448 h1 v-448">
<path d="M144 48 v448 h1 v-448">
<path d="M176 48 v448 h1 v-448">
<path d="M208 48 v448 h1 v-448">
<path d="M240 48 v448 h1 v-448">
<path d="M272 48 v448 h1 v-448">
<path d="M304 48 v448 h1 v-448">
<path d="M336 48 v448 h1 v-448">
<path d="M368 48 v448 h1 v-448">
<path d="M400 48 v448 h1 v-448">
<path d="M432 48 v448 h1 v-448">
<path d="M464 48 v448 h1 v-448">
<path d="M496 16 v480 h1 v-480">
</g>
<g fill="red">
<path d="M96  96  l15 -5 v3 h71.5 v4 h-71.5 v3" transform="rotate(45,96,96)"/>
<path d="M160 160 l-5 15 h3 v48 h4 v-48 h3">
<path d="M160 224 l15 -5 v3 h71.5 v4 h-71.5 v3" transform="rotate(45,160,224)"/>
<path d="M224 288 l15 -5 v3 h48 v4 h-48 v3">
<path d="M288 288 l15 -5 v3 h71.5 v4 h-71.5 v3" transform="rotate(45,284,284)"/>
<path d="M352 352 l-5 15 h3 v48 h4 v-48 h3">
<path d="M352 416 l15 -5 v3 h48 v4 h-48 v3">
<path d="M416 416 l15 -5 v3 h71.5 v4 h-71.5 v3" transform="rotate(45,416,416)"/>
</g>
<text x="252" y="42" fill="black" font-size="20">変 更 後</text>
<text x="118" y="74" fill="black" font-size="20">Ａ</text>
<text x="150" y="74" fill="black" font-size="20">Ｂ</text>
<text x="182" y="74" fill="black" font-size="20">Ｅ</text>
<text x="214" y="74" fill="black" font-size="20">Ｆ</text>
<text x="246" y="74" fill="black" font-size="20">Ａ</text>
<text x="278" y="74" fill="black" font-size="20">Ｂ</text>
<text x="310" y="74" fill="black" font-size="20">Ｇ</text>
<text x="342" y="74" fill="black" font-size="20">Ｈ</text>
<text x="374" y="74" fill="black" font-size="20">Ｃ</text>
<text x="406" y="74" fill="black" font-size="20">Ｄ</text>
<text x="438" y="74" fill="black" font-size="20">Ｋ</text>
<text x="470" y="74" fill="black" font-size="20">Ｌ</text>
<text x="22" y="272" fill="black" font-size="20">変</text>
<text x="22" y="298" fill="black" font-size="20">更</text>
<text x="22" y="324" fill="black" font-size="20">前</text>
<text x="54" y="138" fill="black" font-size="20">Ａ</text>
<text x="54" y="170" fill="black" font-size="20">Ｂ</text>
<text x="54" y="202" fill="black" font-size="20">Ｃ</text>
<text x="54" y="234" fill="black" font-size="20">Ｄ</text>
<text x="54" y="266" fill="black" font-size="20">Ｅ</text>
<text x="54" y="298" fill="black" font-size="20">Ｆ</text>
<text x="54" y="330" fill="black" font-size="20">Ｇ</text>
<text x="54" y="362" fill="black" font-size="20">Ｈ</text>
<text x="54" y="394" fill="black" font-size="20">Ｉ</text>
<text x="54" y="426" fill="black" font-size="20">Ｊ</text>
<text x="54" y="458" fill="black" font-size="20">Ｋ</text>
<text x="54" y="490" fill="black" font-size="20">Ｌ</text>

<text x="92"  y="104" fill="black" font-size="16">0</text>
<text x="124" y="104" fill="black" font-size="16">1</text>
<text x="156" y="104" fill="black" font-size="16">2</text>
<text x="188" y="104" fill="black" font-size="16">3</text>
<text x="220" y="104" fill="black" font-size="16">4</text>
<text x="252" y="104" fill="black" font-size="16">5</text>
<text x="284" y="104" fill="black" font-size="16">6</text>
<text x="316" y="104" fill="black" font-size="16">7</text>
<text x="348" y="104" fill="black" font-size="16">8</text>
<text x="380" y="104" fill="black" font-size="16">9</text>
<text x="406" y="104" fill="black" font-size="16">10</text>
<text x="438" y="104" fill="black" font-size="16">11</text>
<text x="470" y="104" fill="black" font-size="16">12</text>

<text x="92"  y="136" fill="black" font-size="16">1</text>
<text x="124" y="136" fill="black" font-size="16">0</text>
<text x="156" y="136" fill="black" font-size="16">1</text>
<text x="188" y="136" fill="black" font-size="16">2</text>
<text x="220" y="136" fill="black" font-size="16">3</text>
<text x="252" y="136" fill="black" font-size="16">4</text>
<text x="284" y="136" fill="black" font-size="16">5</text>
<text x="316" y="136" fill="black" font-size="16">6</text>
<text x="348" y="136" fill="black" font-size="16">7</text>
<text x="380" y="136" fill="black" font-size="16">8</text>
<text x="412" y="136" fill="black" font-size="16">9</text>
<text x="438" y="136" fill="black" font-size="16">10</text>
<text x="470" y="136" fill="black" font-size="16">11</text>

<text x="92"  y="168" fill="black" font-size="16">2</text>
<text x="124" y="168" fill="black" font-size="16">1</text>
<text x="156" y="168" fill="black" font-size="16">0</text>
<text x="188" y="168" fill="black" font-size="16">1</text>
<text x="220" y="168" fill="black" font-size="16">2</text>
<text x="252" y="168" fill="black" font-size="16">3</text>
<text x="284" y="168" fill="black" font-size="16">4</text>
<text x="316" y="168" fill="black" font-size="16">5</text>
<text x="348" y="168" fill="black" font-size="16">6</text>
<text x="380" y="168" fill="black" font-size="16">7</text>
<text x="412" y="168" fill="black" font-size="16">8</text>
<text x="444" y="168" fill="black" font-size="16">9</text>
<text x="470" y="168" fill="black" font-size="16">10</text>

<text x="92"  y="200" fill="black" font-size="16">3</text>
<text x="124" y="200" fill="black" font-size="16">2</text>
<text x="156" y="200" fill="black" font-size="16">1</text>
<text x="188" y="200" fill="black" font-size="16">2</text>
<text x="220" y="200" fill="black" font-size="16">3</text>
<text x="252" y="200" fill="black" font-size="16">4</text>
<text x="284" y="200" fill="black" font-size="16">5</text>
<text x="316" y="200" fill="black" font-size="16">6</text>
<text x="348" y="200" fill="black" font-size="16">7</text>
<text x="380" y="200" fill="black" font-size="16">6</text>
<text x="412" y="200" fill="black" font-size="16">7</text>
<text x="444" y="200" fill="black" font-size="16">8</text>
<text x="476" y="200" fill="black" font-size="16">9</text>

<text x="92"  y="232" fill="black" font-size="16">4</text>
<text x="124" y="232" fill="black" font-size="16">3</text>
<text x="156" y="232" fill="black" font-size="16">2</text>
<text x="188" y="232" fill="black" font-size="16">3</text>
<text x="220" y="232" fill="black" font-size="16">4</text>
<text x="252" y="232" fill="black" font-size="16">5</text>
<text x="284" y="232" fill="black" font-size="16">6</text>
<text x="316" y="232" fill="black" font-size="16">7</text>
<text x="348" y="232" fill="black" font-size="16">8</text>
<text x="380" y="232" fill="black" font-size="16">7</text>
<text x="412" y="232" fill="black" font-size="16">6</text>
<text x="444" y="232" fill="black" font-size="16">7</text>
<text x="476" y="232" fill="black" font-size="16">8</text>

<text x="92"  y="264" fill="black" font-size="16">5</text>
<text x="124" y="264" fill="black" font-size="16">4</text>
<text x="156" y="264" fill="black" font-size="16">3</text>
<text x="188" y="264" fill="black" font-size="16">2</text>
<text x="220" y="264" fill="black" font-size="16">3</text>
<text x="252" y="264" fill="black" font-size="16">4</text>
<text x="284" y="264" fill="black" font-size="16">5</text>
<text x="316" y="264" fill="black" font-size="16">6</text>
<text x="348" y="264" fill="black" font-size="16">7</text>
<text x="380" y="264" fill="black" font-size="16">8</text>
<text x="412" y="264" fill="black" font-size="16">7</text>
<text x="444" y="264" fill="black" font-size="16">8</text>
<text x="476" y="264" fill="black" font-size="16">9</text>

<text x="92"  y="296" fill="black" font-size="16">6</text>
<text x="124" y="296" fill="black" font-size="16">5</text>
<text x="156" y="296" fill="black" font-size="16">4</text>
<text x="188" y="296" fill="black" font-size="16">3</text>
<text x="220" y="296" fill="black" font-size="16">2</text>
<text x="252" y="296" fill="black" font-size="16">3</text>
<text x="284" y="296" fill="black" font-size="16">4</text>
<text x="316" y="296" fill="black" font-size="16">5</text>
<text x="348" y="296" fill="black" font-size="16">6</text>
<text x="380" y="296" fill="black" font-size="16">7</text>
<text x="412" y="296" fill="black" font-size="16">8</text>
<text x="444" y="296" fill="black" font-size="16">9</text>
<text x="470" y="296" fill="black" font-size="16">10</text>

<text x="92"  y="328" fill="black" font-size="16">7</text>
<text x="124" y="328" fill="black" font-size="16">6</text>
<text x="156" y="328" fill="black" font-size="16">5</text>
<text x="188" y="328" fill="black" font-size="16">4</text>
<text x="220" y="328" fill="black" font-size="16">3</text>
<text x="252" y="328" fill="black" font-size="16">4</text>
<text x="284" y="328" fill="black" font-size="16">5</text>
<text x="316" y="328" fill="black" font-size="16">4</text>
<text x="348" y="328" fill="black" font-size="16">5</text>
<text x="380" y="328" fill="black" font-size="16">6</text>
<text x="412" y="328" fill="black" font-size="16">7</text>
<text x="444" y="328" fill="black" font-size="16">8</text>
<text x="476" y="328" fill="black" font-size="16">9</text>

<text x="92"  y="360" fill="black" font-size="16">8</text>
<text x="124" y="360" fill="black" font-size="16">7</text>
<text x="156" y="360" fill="black" font-size="16">6</text>
<text x="188" y="360" fill="black" font-size="16">5</text>
<text x="220" y="360" fill="black" font-size="16">4</text>
<text x="252" y="360" fill="black" font-size="16">5</text>
<text x="284" y="360" fill="black" font-size="16">6</text>
<text x="316" y="360" fill="black" font-size="16">5</text>
<text x="348" y="360" fill="black" font-size="16">4</text>
<text x="380" y="360" fill="black" font-size="16">5</text>
<text x="412" y="360" fill="black" font-size="16">6</text>
<text x="444" y="360" fill="black" font-size="16">7</text>
<text x="476" y="360" fill="black" font-size="16">8</text>

<text x="92"  y="392" fill="black" font-size="16">9</text>
<text x="124" y="392" fill="black" font-size="16">8</text>
<text x="156" y="392" fill="black" font-size="16">7</text>
<text x="188" y="392" fill="black" font-size="16">6</text>
<text x="220" y="392" fill="black" font-size="16">5</text>
<text x="252" y="392" fill="black" font-size="16">6</text>
<text x="284" y="392" fill="black" font-size="16">7</text>
<text x="316" y="392" fill="black" font-size="16">6</text>
<text x="348" y="392" fill="black" font-size="16">5</text>
<text x="380" y="392" fill="black" font-size="16">6</text>
<text x="412" y="392" fill="black" font-size="16">7</text>
<text x="444" y="392" fill="black" font-size="16">8</text>
<text x="476" y="392" fill="black" font-size="16">9</text>

<text x="86"  y="424" fill="black" font-size="16">10</text>
<text x="124" y="424" fill="black" font-size="16">9</text>
<text x="156" y="424" fill="black" font-size="16">8</text>
<text x="188" y="424" fill="black" font-size="16">7</text>
<text x="220" y="424" fill="black" font-size="16">6</text>
<text x="252" y="424" fill="black" font-size="16">7</text>
<text x="284" y="424" fill="black" font-size="16">8</text>
<text x="316" y="424" fill="black" font-size="16">7</text>
<text x="348" y="424" fill="black" font-size="16">6</text>
<text x="380" y="424" fill="black" font-size="16">7</text>
<text x="412" y="424" fill="black" font-size="16">8</text>
<text x="444" y="424" fill="black" font-size="16">9</text>
<text x="470" y="424" fill="black" font-size="16">10</text>

<text x="86"  y="456" fill="black" font-size="16">11</text>
<text x="118" y="456" fill="black" font-size="16">10</text>
<text x="156" y="456" fill="black" font-size="16">9</text>
<text x="188" y="456" fill="black" font-size="16">8</text>
<text x="220" y="456" fill="black" font-size="16">7</text>
<text x="252" y="456" fill="black" font-size="16">8</text>
<text x="284" y="456" fill="black" font-size="16">9</text>
<text x="316" y="456" fill="black" font-size="16">8</text>
<text x="348" y="456" fill="black" font-size="16">7</text>
<text x="380" y="456" fill="black" font-size="16">8</text>
<text x="412" y="456" fill="black" font-size="16">9</text>
<text x="444" y="456" fill="black" font-size="16">8</text>
<text x="476" y="456" fill="black" font-size="16">9</text>

<text x="86"  y="488" fill="black" font-size="16">12</text>
<text x="118" y="488" fill="black" font-size="16">11</text>
<text x="150" y="488" fill="black" font-size="16">10</text>
<text x="188" y="488" fill="black" font-size="16">9</text>
<text x="220" y="488" fill="black" font-size="16">8</text>
<text x="252" y="488" fill="black" font-size="16">9</text>
<text x="278" y="488" fill="black" font-size="16">10</text>
<text x="316" y="488" fill="black" font-size="16">9</text>
<text x="348" y="488" fill="black" font-size="16">8</text>
<text x="380" y="488" fill="black" font-size="16">9</text>
<text x="406" y="488" fill="black" font-size="16">10</text>
<text x="444" y="488" fill="black" font-size="16">9</text>
<text x="476" y="488" fill="black" font-size="16">8</text>

<text x="56" y="526" fill="black" font-size="16">ｉ</text>
<text x="510" y="72" fill="black" font-size="16">ｊ</text>
<path d="M506 80 h15 v-3 l15 4 l-15 4 v-3 h-15" fill="black">
<path d="M80 508 v15 h-3 l 4 15 l4 -15 h-3 v-15" fill="black">
</svg>
title
<$FIGURE>
図５　最短経路を終点から辿る
end title
@endum
```

ちなみに終点のマスの距離がゼロの場合，二つのファイルは完全一致していることになる。

# 3. 差分の出力

差分の出力サンプルを以下に示す。Windows 付属の `FC` コマンドに準じ，不一致部分を挟んで前後の一致部分を一行だけ出力するものとする。

```plantuml
@startuml
<style>
root {
  margin 0
  paddiing 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="600" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h150 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">差分の出力サンプル</text>
</svg>
title
<$TITLE>

<code>
***** 変更前
Ｂ
Ｃ
Ｄ
Ｅ
***** 変更後
Ｂ
Ｅ
*****

***** 変更前
Ｆ
Ｇ
***** 変更後
Ｆ
Ａ
Ｂ
Ｇ
*****

***** 変更前
Ｈ
Ｉ
Ｊ
Ｋ
***** 変更後
Ｈ
Ｃ
Ｄ
Ｋ
*****
</code>
end title
@enduml
```

これをマップで示すと以下のようになる。一致するマス `○` が連続する場合を除き，一致するマスから次の一致するマスまでの部分経路（下図の<font color=red>▢</font>の範囲）を出力すればよい。

```plantuml
@startuml
<style>
root {
  margin: 0;
  padding: 0;
}
title {
  fontSize: 16;
  fontStyle: normal;
}
</style>
sprite FIGURE <svg width="544" height="544">
<g fill="lightblue">
<path d="M80 80 h416 v32 h-416">
<path d="M80 80 v416 h32 v-416">
</g>
<g fill="lightgray">
<path d="M112 112 h32 v32 h-32">
<path d="M144 144 h32 v32 h-32">
<path d="M176 240 h32 v32 h-32">
<path d="M208 272 h32 v32 h-32">
<path d="M240 112 h32 v32 h-32">
<path d="M272 144 h32 v32 h-32">
<path d="M304 304 h32 v32 h-32">
<path d="M336 336 h32 v32 h-32">
<path d="M368 176 h32 v32 h-32">
<path d="M400 208 h32 v32 h-32">
<path d="M432 432 h32 v32 h-32">
<path d="M464 464 h32 v32 h-32">
</g>
<g fill="yellow">
<path d="M144 176 h32 v32 h-32">
<path d="M144 208 h32 v32 h-32">
<path d="M240 272 h32 v32 h-32">
<path d="M272 272 h32 v32 h-32">
<path d="M336 368 h32 v32 h-32">
<path d="M336 400 h32 v32 h-32">
<path d="M368 400 h32 v32 h-32">
<path d="M400 400 h32 v32 h-32">
</g>
<g fill="black">
<path d="M16 16  h480 v1 h-480">
<path d="M80 48  h416 v1 h-416">
<path d="M16 80  h480 v1 h-480">
<path d="M48 112 h448 v1 h-448">
<path d="M48 144 h448 v1 h-448">
<path d="M48 176 h448 v1 h-448">
<path d="M48 208 h448 v1 h-448">
<path d="M48 240 h448 v1 h-448">
<path d="M48 272 h448 v1 h-448">
<path d="M48 304 h448 v1 h-448">
<path d="M48 336 h448 v1 h-448">
<path d="M48 368 h448 v1 h-448">
<path d="M48 400 h448 v1 h-448">
<path d="M48 432 h448 v1 h-448">
<path d="M48 464 h448 v1 h-448">
<path d="M16 496 h480 v1 h-480">
<path d="M16  16 v480 h1 v-480">
<path d="M48  80 v416 h1 v-416">
<path d="M80  16 v480 h1 v-480">
<path d="M112 48 v448 h1 v-448">
<path d="M144 48 v448 h1 v-448">
<path d="M176 48 v448 h1 v-448">
<path d="M208 48 v448 h1 v-448">
<path d="M240 48 v448 h1 v-448">
<path d="M272 48 v448 h1 v-448">
<path d="M304 48 v448 h1 v-448">
<path d="M336 48 v448 h1 v-448">
<path d="M368 48 v448 h1 v-448">
<path d="M400 48 v448 h1 v-448">
<path d="M432 48 v448 h1 v-448">
<path d="M464 48 v448 h1 v-448">
<path d="M496 16 v480 h1 v-480">
</g>
<text x="252" y="42" fill="black" font-size="20">変 更 後</text>
<text x="118" y="74" fill="black" font-size="20">Ａ</text>
<text x="150" y="74" fill="black" font-size="20">Ｂ</text>
<text x="182" y="74" fill="black" font-size="20">Ｅ</text>
<text x="214" y="74" fill="black" font-size="20">Ｆ</text>
<text x="246" y="74" fill="black" font-size="20">Ａ</text>
<text x="278" y="74" fill="black" font-size="20">Ｂ</text>
<text x="310" y="74" fill="black" font-size="20">Ｇ</text>
<text x="342" y="74" fill="black" font-size="20">Ｈ</text>
<text x="374" y="74" fill="black" font-size="20">Ｃ</text>
<text x="406" y="74" fill="black" font-size="20">Ｄ</text>
<text x="438" y="74" fill="black" font-size="20">Ｋ</text>
<text x="470" y="74" fill="black" font-size="20">Ｌ</text>
<text x="22" y="272" fill="black" font-size="20">変</text>
<text x="22" y="298" fill="black" font-size="20">更</text>
<text x="22" y="324" fill="black" font-size="20">前</text>
<text x="54" y="138" fill="black" font-size="20">Ａ</text>
<text x="54" y="170" fill="black" font-size="20">Ｂ</text>
<text x="54" y="202" fill="black" font-size="20">Ｃ</text>
<text x="54" y="234" fill="black" font-size="20">Ｄ</text>
<text x="54" y="266" fill="black" font-size="20">Ｅ</text>
<text x="54" y="298" fill="black" font-size="20">Ｆ</text>
<text x="54" y="330" fill="black" font-size="20">Ｇ</text>
<text x="54" y="362" fill="black" font-size="20">Ｈ</text>
<text x="54" y="394" fill="black" font-size="20">Ｉ</text>
<text x="54" y="426" fill="black" font-size="20">Ｊ</text>
<text x="54" y="458" fill="black" font-size="20">Ｋ</text>
<text x="54" y="490" fill="black" font-size="20">Ｌ</text>

<text x="92"  y="104" fill="black" font-size="16">0</text>
<text x="124" y="104" fill="black" font-size="16">1</text>
<text x="156" y="104" fill="black" font-size="16">2</text>
<text x="188" y="104" fill="black" font-size="16">3</text>
<text x="220" y="104" fill="black" font-size="16">4</text>
<text x="252" y="104" fill="black" font-size="16">5</text>
<text x="284" y="104" fill="black" font-size="16">6</text>
<text x="316" y="104" fill="black" font-size="16">7</text>
<text x="348" y="104" fill="black" font-size="16">8</text>
<text x="380" y="104" fill="black" font-size="16">9</text>
<text x="406" y="104" fill="black" font-size="16">10</text>
<text x="438" y="104" fill="black" font-size="16">11</text>
<text x="470" y="104" fill="black" font-size="16">12</text>

<text x="92"  y="136" fill="black" font-size="16">1</text>
<text x="124" y="136" fill="black" font-size="16">0</text>
<text x="156" y="136" fill="black" font-size="16">1</text>
<text x="188" y="136" fill="black" font-size="16">2</text>
<text x="220" y="136" fill="black" font-size="16">3</text>
<text x="252" y="136" fill="black" font-size="16">4</text>
<text x="284" y="136" fill="black" font-size="16">5</text>
<text x="316" y="136" fill="black" font-size="16">6</text>
<text x="348" y="136" fill="black" font-size="16">7</text>
<text x="380" y="136" fill="black" font-size="16">8</text>
<text x="412" y="136" fill="black" font-size="16">9</text>
<text x="438" y="136" fill="black" font-size="16">10</text>
<text x="470" y="136" fill="black" font-size="16">11</text>

<text x="92"  y="168" fill="black" font-size="16">2</text>
<text x="124" y="168" fill="black" font-size="16">1</text>
<text x="156" y="168" fill="black" font-size="16">0</text>
<text x="188" y="168" fill="black" font-size="16">1</text>
<text x="220" y="168" fill="black" font-size="16">2</text>
<text x="252" y="168" fill="black" font-size="16">3</text>
<text x="284" y="168" fill="black" font-size="16">4</text>
<text x="316" y="168" fill="black" font-size="16">5</text>
<text x="348" y="168" fill="black" font-size="16">6</text>
<text x="380" y="168" fill="black" font-size="16">7</text>
<text x="412" y="168" fill="black" font-size="16">8</text>
<text x="444" y="168" fill="black" font-size="16">9</text>
<text x="470" y="168" fill="black" font-size="16">10</text>

<text x="92"  y="200" fill="black" font-size="16">3</text>
<text x="124" y="200" fill="black" font-size="16">2</text>
<text x="156" y="200" fill="black" font-size="16">1</text>
<text x="188" y="200" fill="black" font-size="16">2</text>
<text x="220" y="200" fill="black" font-size="16">3</text>
<text x="252" y="200" fill="black" font-size="16">4</text>
<text x="284" y="200" fill="black" font-size="16">5</text>
<text x="316" y="200" fill="black" font-size="16">6</text>
<text x="348" y="200" fill="black" font-size="16">7</text>
<text x="380" y="200" fill="black" font-size="16">6</text>
<text x="412" y="200" fill="black" font-size="16">7</text>
<text x="444" y="200" fill="black" font-size="16">8</text>
<text x="476" y="200" fill="black" font-size="16">9</text>

<text x="92"  y="232" fill="black" font-size="16">4</text>
<text x="124" y="232" fill="black" font-size="16">3</text>
<text x="156" y="232" fill="black" font-size="16">2</text>
<text x="188" y="232" fill="black" font-size="16">3</text>
<text x="220" y="232" fill="black" font-size="16">4</text>
<text x="252" y="232" fill="black" font-size="16">5</text>
<text x="284" y="232" fill="black" font-size="16">6</text>
<text x="316" y="232" fill="black" font-size="16">7</text>
<text x="348" y="232" fill="black" font-size="16">8</text>
<text x="380" y="232" fill="black" font-size="16">7</text>
<text x="412" y="232" fill="black" font-size="16">6</text>
<text x="444" y="232" fill="black" font-size="16">7</text>
<text x="476" y="232" fill="black" font-size="16">8</text>

<text x="92"  y="264" fill="black" font-size="16">5</text>
<text x="124" y="264" fill="black" font-size="16">4</text>
<text x="156" y="264" fill="black" font-size="16">3</text>
<text x="188" y="264" fill="black" font-size="16">2</text>
<text x="220" y="264" fill="black" font-size="16">3</text>
<text x="252" y="264" fill="black" font-size="16">4</text>
<text x="284" y="264" fill="black" font-size="16">5</text>
<text x="316" y="264" fill="black" font-size="16">6</text>
<text x="348" y="264" fill="black" font-size="16">7</text>
<text x="380" y="264" fill="black" font-size="16">8</text>
<text x="412" y="264" fill="black" font-size="16">7</text>
<text x="444" y="264" fill="black" font-size="16">8</text>
<text x="476" y="264" fill="black" font-size="16">9</text>

<text x="92"  y="296" fill="black" font-size="16">6</text>
<text x="124" y="296" fill="black" font-size="16">5</text>
<text x="156" y="296" fill="black" font-size="16">4</text>
<text x="188" y="296" fill="black" font-size="16">3</text>
<text x="220" y="296" fill="black" font-size="16">2</text>
<text x="252" y="296" fill="black" font-size="16">3</text>
<text x="284" y="296" fill="black" font-size="16">4</text>
<text x="316" y="296" fill="black" font-size="16">5</text>
<text x="348" y="296" fill="black" font-size="16">6</text>
<text x="380" y="296" fill="black" font-size="16">7</text>
<text x="412" y="296" fill="black" font-size="16">8</text>
<text x="444" y="296" fill="black" font-size="16">9</text>
<text x="470" y="296" fill="black" font-size="16">10</text>

<text x="92"  y="328" fill="black" font-size="16">7</text>
<text x="124" y="328" fill="black" font-size="16">6</text>
<text x="156" y="328" fill="black" font-size="16">5</text>
<text x="188" y="328" fill="black" font-size="16">4</text>
<text x="220" y="328" fill="black" font-size="16">3</text>
<text x="252" y="328" fill="black" font-size="16">4</text>
<text x="284" y="328" fill="black" font-size="16">5</text>
<text x="316" y="328" fill="black" font-size="16">4</text>
<text x="348" y="328" fill="black" font-size="16">5</text>
<text x="380" y="328" fill="black" font-size="16">6</text>
<text x="412" y="328" fill="black" font-size="16">7</text>
<text x="444" y="328" fill="black" font-size="16">8</text>
<text x="476" y="328" fill="black" font-size="16">9</text>

<text x="92"  y="360" fill="black" font-size="16">8</text>
<text x="124" y="360" fill="black" font-size="16">7</text>
<text x="156" y="360" fill="black" font-size="16">6</text>
<text x="188" y="360" fill="black" font-size="16">5</text>
<text x="220" y="360" fill="black" font-size="16">4</text>
<text x="252" y="360" fill="black" font-size="16">5</text>
<text x="284" y="360" fill="black" font-size="16">6</text>
<text x="316" y="360" fill="black" font-size="16">5</text>
<text x="348" y="360" fill="black" font-size="16">4</text>
<text x="380" y="360" fill="black" font-size="16">5</text>
<text x="412" y="360" fill="black" font-size="16">6</text>
<text x="444" y="360" fill="black" font-size="16">7</text>
<text x="476" y="360" fill="black" font-size="16">8</text>

<text x="92"  y="392" fill="black" font-size="16">9</text>
<text x="124" y="392" fill="black" font-size="16">8</text>
<text x="156" y="392" fill="black" font-size="16">7</text>
<text x="188" y="392" fill="black" font-size="16">6</text>
<text x="220" y="392" fill="black" font-size="16">5</text>
<text x="252" y="392" fill="black" font-size="16">6</text>
<text x="284" y="392" fill="black" font-size="16">7</text>
<text x="316" y="392" fill="black" font-size="16">6</text>
<text x="348" y="392" fill="black" font-size="16">5</text>
<text x="380" y="392" fill="black" font-size="16">6</text>
<text x="412" y="392" fill="black" font-size="16">7</text>
<text x="444" y="392" fill="black" font-size="16">8</text>
<text x="476" y="392" fill="black" font-size="16">9</text>

<text x="86"  y="424" fill="black" font-size="16">10</text>
<text x="124" y="424" fill="black" font-size="16">9</text>
<text x="156" y="424" fill="black" font-size="16">8</text>
<text x="188" y="424" fill="black" font-size="16">7</text>
<text x="220" y="424" fill="black" font-size="16">6</text>
<text x="252" y="424" fill="black" font-size="16">7</text>
<text x="284" y="424" fill="black" font-size="16">8</text>
<text x="316" y="424" fill="black" font-size="16">7</text>
<text x="348" y="424" fill="black" font-size="16">6</text>
<text x="380" y="424" fill="black" font-size="16">7</text>
<text x="412" y="424" fill="black" font-size="16">8</text>
<text x="444" y="424" fill="black" font-size="16">9</text>
<text x="470" y="424" fill="black" font-size="16">10</text>

<text x="86"  y="456" fill="black" font-size="16">11</text>
<text x="118" y="456" fill="black" font-size="16">10</text>
<text x="156" y="456" fill="black" font-size="16">9</text>
<text x="188" y="456" fill="black" font-size="16">8</text>
<text x="220" y="456" fill="black" font-size="16">7</text>
<text x="252" y="456" fill="black" font-size="16">8</text>
<text x="284" y="456" fill="black" font-size="16">9</text>
<text x="316" y="456" fill="black" font-size="16">8</text>
<text x="348" y="456" fill="black" font-size="16">7</text>
<text x="380" y="456" fill="black" font-size="16">8</text>
<text x="412" y="456" fill="black" font-size="16">9</text>
<text x="444" y="456" fill="black" font-size="16">8</text>
<text x="476" y="456" fill="black" font-size="16">9</text>

<text x="86"  y="488" fill="black" font-size="16">12</text>
<text x="118" y="488" fill="black" font-size="16">11</text>
<text x="150" y="488" fill="black" font-size="16">10</text>
<text x="188" y="488" fill="black" font-size="16">9</text>
<text x="220" y="488" fill="black" font-size="16">8</text>
<text x="252" y="488" fill="black" font-size="16">9</text>
<text x="278" y="488" fill="black" font-size="16">10</text>
<text x="316" y="488" fill="black" font-size="16">9</text>
<text x="348" y="488" fill="black" font-size="16">8</text>
<text x="380" y="488" fill="black" font-size="16">9</text>
<text x="406" y="488" fill="black" font-size="16">10</text>
<text x="444" y="488" fill="black" font-size="16">9</text>
<text x="476" y="488" fill="black" font-size="16">8</text>

<text x="56" y="526" fill="black" font-size="16">ｉ</text>
<text x="510" y="72" fill="black" font-size="16">ｊ</text>
<path d="M506 80 h15 v-3 l15 4 l-15 4 v-3 h-15" fill="black">
<path d="M80 508 v15 h-3 l 4 15 l4 -15 h-3 v-15" fill="black">

<g fill="red">
<path d="M143 143 h66 v3 h-66">
<path d="M143 271 h66 v3 h-66">
<path d="M143 143 v130 h3 v-130">
<path d="M207 143 v130 h3 v-130">

<path d="M207 271 h130 v3 h-130">
<path d="M207 335 h130 v3 h-130">
<path d="M207 271 v66 h3 v-66">
<path d="M335 271 v66 h3 v-66">

<path d="M335 335 h130 v3 h-130">
<path d="M335 463 h130 v3 h-130">
<path d="M335 335 v130 h3 v-130">
<path d="M463 335 v130 h3 v-130">
</g>
</svg>
title
<$FIGURE>
図６　データ出力
end title
@endum
```

# 4. 実装コード

## 4.1 ファイルの読み込み

文字コードはシステムデフォルト値としてファイルをオープンするが，ファイルの先頭に BOM がある場合は BOM を優先する。入力ファイルの行数 $N$ とすると，整数 $i$ を用いて $1 \le i \le N$ の範囲でリストにアクセスできるよう，先頭にダミーとして空行を入れる。

```c#:ファイルの読み込み
static	List<string>	load_file( string filename ) {
	if( !File.Exists( filename ) ) {
		Console.Error.WriteLine( "ファイル {0} を開けません。このファイルは存在しません",
			filename );
		return null;
	}
	var	line = new List<string>();
	var	reader = new StreamReader( filename, Encoding.Default, true );
	line.Add( "" );
	while( !reader.EndOfStream ) {
		var	s = reader.ReadLine();
		line.Add( s );
	}
	return line;
}
```

## 4.2 照合マップの作成

二つの入力ファイルの行数をそれぞれ $M$, $N$ とおくと，全行を読み込んだリスト `line1`，`line2` の長さは先頭にダミー行を追加したため $M + 1$，$N + 1$ となる。照合マップは二次元配列であり，サイズは $(M + 1)\times (N + 1)$ となる。なお C# は多次元配列を公式サポートしている言語であるが，C# の多次元配列は非常に遅いことで有名なため，代わりにジャグ配列を用いた。

```c#:照合マップの作成
static	bool[][]	make_cmap( List<string> line1, List<string> line2 ) {
	var	hash1 = make_hash( line1 );
	var	hash2 = make_hash( line2 );
	var	cmap = new bool[line1.Count][];
	for( int i = 0; i < line1.Count; i++ )
		cmap[i] = new bool[line2.Count];
	for( int i = 1; i < line1.Count; i++ )
		for( int j = 1; j < line2.Count; j++ )
			if( hash1[i] != hash2[j] )
				cmap[i][j] = false;
			else if( 0 != string.Compare( line1[i], line2[j] ) )
				cmap[i][j] = false;
			else
				cmap[i][j] = true;
	return cmap;
}
```

照合マップの作成は比較的重い処理になるため，ハッシュ値を用いて文字列比較を高速化する。ハッシュ関数は単なる文字列のサム値とした。

```c#:ハッシュの作成
static	int[]	make_hash( List<string> line ) {
	var	hash = new int[line.Count];
	for( int i = 0; i < line.Count; i++ ) {
		var	s = line[i];
		int	sum = 0;
		for( int j = 0; j < s.Length; j++ )
			sum += (int)s[j];
		hash[i] = sum;
	}
	return hash;
}
```

## 4.3 距離マップの作成

距離マップも二次元配列であり，こちらもジャグ配列にする。サイズは $(M + 1)\times (N + 1)$ となる。

```c#:距離マップの作成
static	int[][]	make_dmap( bool[][] cmap ) {
	var	dmap = new int[cmap.Length][];
	for( int i = 0; i < cmap.Length; i++ )
		dmap[i] = new int[cmap[0].Length];
	dmap[0][0] = 0;
	for( int i = 1; i < dmap.Length; i++ )
		dmap[i][0] = i;
	for( int j = 1; j < dmap[0].Length; j++ )
		dmap[0][j] = j;
	for( int i = 1; i < dmap.Length; i++ ) {
		for( int j = 1; j < dmap[0].Length; j++ ) {
			int	d = Math.Min( dmap[i - 1][j], dmap[i][j - 1] ) + 1;
			if( cmap[i][j] )
				d = Math.Min( d, dmap[i - 1][j - 1] );
			dmap[i][j] = d;
		}
	}
	return dmap;
}
```

## 4.4 最短経路の生成

パス型 `PATH` を以下のように定義する。

```c#:パス型の定義
enum PATH : int {
	DELETE = -1,
	MATCH  = 0,
	INSERT = 1
}
```

最短経路は終点から始点まで逆順にサーチして，最後にリストを反転する。

```c#:最短経路の生成
static	List<PATH>	make_path( bool[][] cmap, int[][] dmap ) {
	var	path = new List<PATH>();
	int	i = dmap.Length    - 1;
	int	j = dmap[0].Length - 1;
	while( true ) {
		if( i == 0 && j == 0 ) {
			break;
		} else if( i == 0 ) {
			path.Add( PATH.INSERT ); j--;
		} else if( j == 0 ) {
			path.Add( PATH.DELETE ); i--;
		} else if( cmap[i][j] && dmap[i - 1][j - 1] <= dmap[i][j - 1]
							  && dmap[i - 1][j - 1] <= dmap[i - 1][j] ) {
			path.Add( PATH.MATCH  ); i--; j--;
		} else if( dmap[i][j - 1] <= dmap[i - 1][j] ) {
			path.Add( PATH.INSERT ); j--;
		} else {
			path.Add( PATH.DELETE ); i--;
		}
	}
	path.Reverse();
	return path;
}
 ```

## 4.5 差分情報の出力

似たような処理を繰り返すことからローカル関数を用いるとすっきり記述することができる。ところが Windows に付属する C# コンパイラ（バージョン 4.0）ではローカル関数をサポートしていないので delegate で代用することにした。

```c#:ローカル関数代用の delegate 型の定義
delegate	void	LOCALFUNC();
```

```c#:差分情報の出力
static	void	show_diff( List<PATH> path, List<string> line1, List<string> line2 ) {
	int	start1 = 1, end1 = 0;
	int	start2 = 1, end2 = 0;
	PATH	prev = PATH.MATCH;
	//----------------------------------------------------------------------
	// 出力用ローカル関数
	//----------------------------------------------------------------------
	LOCALFUNC	output = delegate() {
		Console.WriteLine( "***** " + filename1 );
		for( int i = start1; i <= end1; i++ ) {
			if( line_number ) Console.Write( "{0,5:D}:  ", i );
			Console.WriteLine( line1[i] );
		}
		Console.WriteLine( "***** " + filename2 );
		for( int i = start2; i <= end2; i++ ) {
			if( line_number ) Console.Write( "{0,5:D}:  ", i );
			Console.WriteLine( line2[i] );
		}
		Console.WriteLine( "*****" );
		Console.WriteLine( "" );
	};
	for( int i = 0; i < path.Count; i++ ) {
		switch( path[i] ) {
		  case PATH.MATCH:
			end1++;
			end2++;
			if( prev != PATH.MATCH ) output();
			start1 = end1;
			start2 = end2;
			break;
		  case PATH.INSERT:
			end2++;
			break;
		  case PATH.DELETE:
			end1++;
			break;
		}
		prev = path[i];
	}
	if( prev != PATH.MATCH ) output();
}
```

## 4.6 実装コード

実装コードを以下に示す。Windows 付属の C# コンパイラ（バージョン4.0）でもコンパイルできるように設計した。もちろん Visual Studio 付属の C# コンパイラでも問題なくコンパイル可能である。

<details><summary><b>DIFF.CS の実装コードはコチラ</b></summary>

```C#:DIFF.CS
//------------------------------------------------------------------------------
// 2 つのファイルを比較し、相違点を表示します。
//------------------------------------------------------------------------------
using System;
using System.IO;
using System.Text;
using System.Reflection;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Runtime.InteropServices;
//------------------------------------------------------------------------------
// 差分クラス
//------------------------------------------------------------------------------
class DIFF {
	//--------------------------------------------------------------------------
	// 定数定義
	//--------------------------------------------------------------------------
	enum PATH : int {
		DELETE = -1,
		MATCH  = 0,
		INSERT = 1
	}
	//--------------------------------------------------------------------------
	// グローバル変数
	//--------------------------------------------------------------------------
	static	string	filename1   = "";		// ファイル名(1)
	static	string	filename2   = "";		// ファイル名(2)
	static	bool	line_number = false;	// 行番号を表示する
	//--------------------------------------------------------------------------
	// ヘルプメッセージ
	//--------------------------------------------------------------------------
	static	int	usage() {
		Console.Error.WriteLine( "2 つのファイルを比較し、相違点を表示します。" );
		Console.Error.WriteLine( "" );
		Console.Error.WriteLine( "DIFF(.EXE) (オプション) [ファイル名1] [ファイル名2]" );
		Console.Error.WriteLine( "" );
		Console.Error.WriteLine( "/N　行番号を表示します。" );
		return -1;
	}
	//--------------------------------------------------------------------------
	// オプション解析
	//--------------------------------------------------------------------------
	static	int	get_option( string[] args ) {
		foreach( string s in args ) {
			if( s[0] == '-' || s[0] == '/' ) {
				switch( s[1] ) {
				  case 'N': case 'n':
					line_number = true;
					break;
				  default:
					Console.Error.WriteLine( "不正なオプションです：{0}", s );
					return -1;
				}
			} else if( filename1 == "" ) {
				filename1 = s;
			} else if( filename2 == "" ) {
				filename2 = s;
			} else {
				Console.Error.WriteLine( "入力ファイル名は既に指定されています!!" );
				return -1;
			}
		}
		if( filename1 == "" || filename2 == "" ) return usage();
		return 0;
	}
	//--------------------------------------------------------------------------
	// ファイルの読み込み
	//--------------------------------------------------------------------------
	static	List<string>	load_file( string filename ) {
		if( !File.Exists( filename ) ) {
			Console.Error.WriteLine( "ファイル {0} を開けません。このファイルは存在しません",
				filename );
			return null;
		}
		var	reader = new StreamReader( filename, Encoding.Default, true );
		var	line = new List<string>();
		line.Add( "" );
		while( !reader.EndOfStream ) {
			var	s = reader.ReadLine();
			line.Add( s );
		}
		return line;
	}
	//--------------------------------------------------------------------------
	// ハッシュの作成
	//--------------------------------------------------------------------------
	static	int[]	make_hash( List<string> line ) {
		var	hash = new int[line.Count];
		for( int i = 0; i < line.Count; i++ ) {
			var	s = line[i];
			int	sum = 0;
			for( int j = 0; j < s.Length; j++ )
				sum += (int)s[j];
			hash[i] = sum;
		}
		return hash;
	}
	//--------------------------------------------------------------------------
	// 照合マップの作成
	//--------------------------------------------------------------------------
	static	bool[][]	make_cmap( List<string> line1, List<string> line2 ) {
		var	hash1 = make_hash( line1 );
		var	hash2 = make_hash( line2 );
		var	cmap = new bool[line1.Count][];
		for( int i = 0; i < line1.Count; i++ )
			cmap[i] = new bool[line2.Count];
		for( int i = 0; i < line1.Count; i++ )
			for( int j = 0; j < line2.Count; j++ )
				if( hash1[i] != hash2[j] )
					cmap[i][j] = false;
				else if( 0 != string.Compare( line1[i], line2[j] ) )
					cmap[i][j] = false;
				else
					cmap[i][j] = true;
		return cmap;
	}
	//--------------------------------------------------------------------------
	// 距離マップの作成
	//--------------------------------------------------------------------------
	static	int[][]	make_dmap( bool[][] cmap ) {
		var	dmap = new int[cmap.Length][];
		for( int i = 0; i < cmap.Length; i++ )
			dmap[i] = new int[cmap[0].Length];
		dmap[0][0] = 0;
		for( int i = 1; i < dmap.Length; i++ )
			dmap[i][0] = i;
		for( int j = 1; j < dmap[0].Length; j++ )
			dmap[0][j] = j;
		for( int i = 1; i < dmap.Length; i++ ) {
			for( int j = 1; j < dmap[0].Length; j++ ) {
				int	d = Math.Min( dmap[i - 1][j], dmap[i][j - 1] ) + 1;
				if( cmap[i][j] )
					d = Math.Min( d, dmap[i - 1][j - 1] );
				dmap[i][j] = d;
			}
		}
		return dmap;
	}
	//--------------------------------------------------------------------------
	// 最短経路の生成
	//--------------------------------------------------------------------------
	static	List<PATH>	make_path( bool[][] cmap, int[][] dmap ) {
		var	path = new List<PATH>();
		int	i = dmap.Length    - 1;
		int	j = dmap[0].Length - 1;
		while( true ) {
			if( i == 0 && j == 0 ) {
				break;
			} else if( i == 0 ) {
				path.Add( PATH.INSERT ); j--;
			} else if( j == 0 ) {
				path.Add( PATH.DELETE ); i--;
			} else if( cmap[i][j] && dmap[i - 1][j - 1] <= dmap[i][j - 1]
								  && dmap[i - 1][j - 1] <= dmap[i - 1][j] ) {
				path.Add( PATH.MATCH  ); i--; j--;
			} else if( dmap[i][j - 1] <= dmap[i - 1][j] ) {
				path.Add( PATH.INSERT ); j--;
			} else {
				path.Add( PATH.DELETE ); i--;
			}
		}
		path.Reverse();
		return path;
	}
	//--------------------------------------------------------------------------
	// ローカル関数型の定義
	//--------------------------------------------------------------------------
	delegate	void	LOCALFUNC();
	//--------------------------------------------------------------------------
	// 差分情報の出力
	//--------------------------------------------------------------------------
	static	void	show_diff( List<PATH> path, List<string> line1, List<string> line2 ) {
		int	start1 = 1, end1 = 0;
		int	start2 = 1, end2 = 0;
		PATH	prev = PATH.MATCH;;
		//----------------------------------------------------------------------
		// 出力用ローカル関数
		//----------------------------------------------------------------------
		LOCALFUNC	output = delegate() {
			Console.WriteLine( "***** " + filename1 );
			for( int i = start1; i <= end1; i++ ) {
				if( line_number ) Console.Write( "{0,5:D}:  ", i );
				Console.WriteLine( line1[i] );
			}
			Console.WriteLine( "***** " + filename2 );
			for( int i = start2; i <= end2; i++ ) {
				if( line_number ) Console.Write( "{0,5:D}:  ", i );
				Console.WriteLine( line2[i] );
			}
			Console.WriteLine( "*****" );
			Console.WriteLine( "" );
		};
		for( int i = 0; i < path.Count; i++ ) {
			switch( path[i] ) {
			  case PATH.MATCH:
				end1++;
				end2++;
				if( prev != PATH.MATCH ) output();
				start1 = end1;
				start2 = end2;
				break;
			  case PATH.INSERT:
				end2++;
				break;
			  case PATH.DELETE:
				end1++;
				break;
			}
			prev = path[i];
		}
		if( prev != PATH.MATCH ) output();
	}
	//--------------------------------------------------------------------------
	// メイン関数
	//--------------------------------------------------------------------------
	static	int		Main( string[] args ) {
		//----------------------------------------------------------------------
		// ヘルプメッセージ
		//----------------------------------------------------------------------
		if( args.Length == 0 ) return usage();
		//----------------------------------------------------------------------
		// オプション解析
		//----------------------------------------------------------------------
		if( get_option( args ) != 0 ) return -1;
		//----------------------------------------------------------------------
		// ファイルの比較
		//----------------------------------------------------------------------
		Console.WriteLine( "ファイル {0} と {1} を比較しています", filename1, filename2 );
		//----------------------------------------------------------------------
		// ファイルの読み込み
		//----------------------------------------------------------------------
		var	line1 = load_file( filename1 ); if( line1 == null ) return -1;
		var	line2 = load_file( filename2 ); if( line2 == null ) return -1;
		//----------------------------------------------------------------------
		// 照合マップの作成
		//----------------------------------------------------------------------
		var	cmap = make_cmap( line1, line2 );
		//----------------------------------------------------------------------
		// 距離マップの作成
		//----------------------------------------------------------------------
		var	dmap = make_dmap( cmap );
		//----------------------------------------------------------------------
		// 距離マップの右下端が 0 なら 2 つのファイルは完全一致
		//----------------------------------------------------------------------
		if( dmap[dmap.Length - 1][dmap[0].Length - 1] == 0 ) {
			Console.WriteLine( "DIFF: 相違点は検出されませんでした" );
			Console.WriteLine( "" );
			return 0;
		}
		//----------------------------------------------------------------------
		// 最短経路の生成
		//----------------------------------------------------------------------
		var	path = make_path( cmap, dmap );
		//----------------------------------------------------------------------
		// 差分情報の出力
		//----------------------------------------------------------------------
		show_diff( path, line1, line2 );
		path.Clear();
		line1.Clear();
		line2.Clear();
		return 1;
	}
}
```

</details>

Windows 付属の C# コンパイラにパスを通すバッチファイル `SETCSC.CMD` のコードも以下に示す。

<details><summary><b>SETCSC.CMD のコードはコチラ</b></summary>

```:SETCSC.CMD
@echo off
if defined DOTNETPATH (
  echo PATH に %DOTNETPATH% は既に存在します。
  exit /b
)
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v Version`
) do (
  if "%%I"=="Version" set "DOTNETVERSION=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
echo PATH に %DOTNETPATH% を追加しました。
```

</details>

# 5. 実行例

引数なしで実行するとヘルプメッセージを表示する。エラーコードは -1 となる。

```plantuml
@startuml
<style>
root {
  margin 0
  paddiing 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="600" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h184 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">引数なしで実行した場合</text>
</svg>
title
<$TITLE>

<code>
C:\>diff
2 つのファイルを比較し、相違点を表示します。

DIFF(.EXE) (オプション) [ファイル名1] [ファイル名2]

/N　行番号を表示します。

C:\>echo %errorlevel%
-1
</code>
end title
@enduml
```

ファイルが一致する場合のエラーコードは 0 となる。

```plantuml
@startuml
<style>
root {
  margin 0
  paddiing 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
root {
  margin 0
  paddiing 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="600" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h184 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">ファイルが一致する場合</text>
</svg>
title
<$TITLE>

<code>
C:\>diff SAMPLE1.TXT SAMPLE1.TXT
ファイル SAMPLE1.TXT と SAMPLE1.TXT を比較しています
DIFF: 相違点は検出されませんでした

C:\>echo %errorlevel%
0
</code>
end title
@enduml
```

ファイルが一致しない場合のエラーコードは 1 となる。

```plantuml
@startuml
<style>
root {
  margin 0
  paddiing 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="600" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h300 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">ファイルが不一致の場合（行番号なし）</text>
</svg>
title
<$TITLE>

<code>
C:\>diff SAMPLE1.TXT SAMPLE2.TXT
ファイル SAMPLE1.TXT と SAMPLE2.TXT を比較しています
***** SAMPLE1.TXT
Ｂ
Ｃ
Ｄ
Ｅ
***** SAMPLE2.TXT
Ｂ
Ｅ
*****

***** SAMPLE1.TXT
Ｆ
Ｇ
***** SAMPLE2.TXT
Ｆ
Ａ
Ｂ
Ｇ
*****

***** SAMPLE1.TXT
Ｈ
Ｉ
Ｊ
Ｋ
***** SAMPLE2.TXT
Ｈ
Ｃ
Ｄ
Ｋ
*****

C:\>echo %errorlevel%
1
</code>
end title
@enduml
```

行番号を表示させた場合を以下に示す。

```plantuml
@startuml
<style>
root {
  margin 0
  paddiing 0
}
title {
  roundCorner 16
  padding 0 16 16 16
  horizontalAlignment left
  backgroundColor black
  fontColor white
  fontStyle normal
}
</style>
sprite TITLE <svg width="600" height="32">
<path d="M0 0 v28 a4 4 0 0 0 4 4 h300 a4 4 0 0 0 4 -4 v-28" fill="#606060" />
<text x="8" y="24" font-size="16" fill="white">ファイルが不一致の場合（行番号表示）</text>
</svg>
title
<$TITLE>

<code>
C:\>diff SAMPLE1.TXT SAMPLE2.TXT /N
ファイル SAMPLE1.TXT と SAMPLE2.TXT を比較しています
***** SAMPLE1.TXT
    2:  Ｂ
    3:  Ｃ
    4:  Ｄ
    5:  Ｅ
***** SAMPLE2.TXT
    2:  Ｂ
    3:  Ｅ
*****

***** SAMPLE1.TXT
    6:  Ｆ
    7:  Ｇ
***** SAMPLE2.TXT
    4:  Ｆ
    5:  Ａ
    6:  Ｂ
    7:  Ｇ
*****

***** SAMPLE1.TXT
    8:  Ｈ
    9:  Ｉ
   10:  Ｊ
   11:  Ｋ
***** SAMPLE2.TXT
    8:  Ｈ
    9:  Ｃ
   10:  Ｄ
   11:  Ｋ
*****

C:\>echo %errorlevel%
1
</code>
end title
@enduml
```

# 6. 今後の課題

<dl>
<dt>(1) 比較するファイルサイズ（行数）の制限</dt>
<dd>比較する二つのファイルの行数の積 $M \times N$ に比例したマップを作成する必要があることから，事実上，数千行程度が上限である。C# プログラムなので 64bit OS であれば広大なメモリを取り扱うことはできるが，さすがに数万行規模に及ぶと計算時間も目立って遅くなる。ただ，もともとこの課題は有名なもので，この課題を解決するために後発のアルゴリズムが開発されたといっても良い。つまり，解決策は無数にある。</dd>
<dt>(2) タブの置換</dt>
<dd>Windows 付属の <code>FC</code> コマンドはデフォルトでタブをスペースに置換してくれる。オプションで置換しないことも選択できる。ただしタブ幅は半角 8 文字分固定である。筆者は 4 文字派なので，置換するタブ幅を変更できるようにしたい。ただし，タブの置換は Unicode の持つ半角／全角問題に向き合う必要があり，真面目にやろうとすると沼にハマりそうで危険な香りがする。</dd>
<dt>(3) 英字の大文字・小文字の区別</dt>
<dd>Windows 付属の <code>FC</code> コマンドはデフォルトで英字の大文字・小文字を区別するが，オプションで区別しないことも選択できる。</dd>
<dt>(4) 連続するスペースの圧縮</dt>
<dd>Windows 付属の <code>FC</code> コマンドはオプションで連続した空白（スペースおよびタブ）を単一のスペースとみなして比較するモードがある。</dd>
</dl>

# 7. 参考文献
- [Algorithm for Computing Maximal Common Subsequence, D.S. Hirschberg, Princeton University <img width=16 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/66e66c9d-a6f3-f215-951a-9d79cc94a9d6.png">](https://dl.acm.org/doi/pdf/10.1145/360825.360861)
- [An Algorithm for Differential File Comparison, J. W. Hunt, Stanford University <img width=16 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/66e66c9d-a6f3-f215-951a-9d79cc94a9d6.png">](https://www.cs.dartmouth.edu/~doug/diff.pdf)
- [An O(ND) Difference Algorithm and Its Variations, W. MYERS <img width=16 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/66e66c9d-a6f3-f215-951a-9d79cc94a9d6.png">](http://www.xmailserver.org/diff2.pdf)
- [レーベンシュタイン距離 - wikipedia](https://ja.wikipedia.org/wiki/レーベンシュタイン距離)
- [diffの動作原理を知る～どのようにして差分を導き出すのか - gihyyo](https://gihyo.jp/dev/column/01/prog/2011/diff_sd200906)
- [Wu らによる差分検出の O(NP) アルゴリズム実装シリーズ ①仕組み、考え方 - Qiita](https://qiita.com/convto/items/e05d8147d9808a27b8ff)
- [コメンデーションとエディットグラフ - itmedia](https://atmarkit.itmedia.co.jp/ait/articles/0905/01/news097.html)
- [文書比較（diff）アルゴリズム - vector](https://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm)
- [diffってなんだ - github](https://gist.github.com/gurimusan/7e554eb12f9f59880053)

- [Version 7 Unix の diff アルゴリズム - tiqwab](https://blog.tiqwab.com/2022/12/11/diff-algorithm-v7unix.html)

- [【動的計画法】最長共通部分列（LCS）- hatenablog](https://programgenjin.hatenablog.com/entry/2019/03/11/081428)