書類仕事に飽きた！ので腕試し。
問題
こんな企画をやってたので遊ぶ。
こういうゲームアルゴリズム大好き...なので島探しをチョイス。
やるならSランクよなぁ！
作戦その1 - 愚直にチェック
こういうのは図で書いたら分かりやすい！
地図用の配列と、島フラグ用の配列を用意する。
- 左上から右下に向かって順番にマスを検査して、島だったら島登録をはじめる。
- 上と左要素を確認して、島だったらその島と同じ島として登録する。
- それ以外は新規の島として扱う。
var lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');
// map を作る
var row = 0
var col = 0
var map = []
for (const key in lines) {
const cells = lines[key].split(' ').map(cell => parseInt(cell))
if (key == 0) {
[col, row] = cells
} else if (key <= row) {
map.push(cells)
}
}
console.log(map)
// 島情報の格納先を作る
var island = [...Array(row)].map(_ => Array(col).fill(0))
// 左上からカーソルを進めて、島をカウントしていく
var islandNo = 0
for (let r = 0; r < row; r++) {
for (let c = 0; c < col; c++) {
// セルが島であれば判定する
if (map[r][c] && !island[r][c]) {
if (r-1 >= 0 && island[r-1][c]) {
// 上要素を確認し、島であれば連結させる
island[r][c] = island[r-1][c]
} else if (c-1 >= 0 && island[r][c-1]) {
// 左要素を確認し、島であれば連結させる
island[r][c] = island[r][c-1]
} else {
// それ以外は新規の島とする
island[r][c] = ++islandNo
}
}
console.log('---', r, c)
console.log(island)
}
}
console.log(map)
console.log(island)
だめじゃん！
左に伸びた半島が検出できない...
作戦その2 - 島を先に探す
ぐぬぬぬ...
こねくり回したが、島を見つけたら先に、その島を探索し終えないといけないかもしれない。
やってみる。
- 左上から右下に向かって順番にマスを検査して、島だったら島登録をはじめる。
- 四方を確認して、島だったら同一の島とする。
- その際に発見した島についても、四方を確認して 2. を繰り返す。
※ 2.3. ループは簡単にするために、スタックを用いた！
var lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');
// map を作る
var row = 0
var col = 0
var map = []
for (const key in lines) {
const cells = lines[key].split(' ').map(cell => parseInt(cell))
if (key == 0) {
[col, row] = cells
} else if (key <= row) {
map.push(cells)
}
}
console.log(map)
// 島情報の格納先を作る
var island = [...Array(row)].map(_ => Array(col).fill(0))
// 左上からカーソルを進めて、島をカウントしていく
var islandNo = 0
for (let r = 0; r < row; r++) {
for (let c = 0; c < col; c++) {
// セルが未発見の島であれば判定を開始する
if (map[r][c] && !island[r][c]) {
// 自身を新規の島にする
island[r][c] = ++islandNo
// 4方向を確認して新規の島を探す
var stack = [[r, c]]
while (stack.length > 0) {
console.log('sub')
console.log(stack)
const [sr, sc] = stack.shift()
if (sr-1 >= 0 && map[sr-1][sc] && !island[sr-1][sc]) {
// 上方向に島があったら染めてpush
island[sr-1][sc] = islandNo
stack.push([sr-1, sc])
}
if (sc-1 >= 0 && map[sr][sc-1] && !island[sr][sc-1]) {
console.log('left')
// 左方向に島があったら染めてpush
island[sr][sc-1] = islandNo
stack.push([sr, sc-1])
}
if (sr+1 < row && map[sr+1][sc] && !island[sr+1][sc]) {
// 下方向に島があったら染めてpush
island[sr+1][sc] = islandNo
stack.push([sr+1, sc])
}
if (sc+1 < col && map[sr][sc+1] && !island[sr][sc+1]) {
// 右方向に島があったら染めてpush
island[sr][sc+1] = islandNo
stack.push([sr, sc+1])
}
}
console.log('end sub')
}
console.log('---', r, c)
console.log(island)
}
}
console.log(map)
console.log(island)
できたじゃん！
なるほどね～先に埋めないといけないのか
作戦その3 - 最適化
作戦2のやり方なら、見つけた島を地図から消していけば、配列一個でも実現できそう。
探索先を減らせないか考えたが、蛇みたいな島が検出できなくなるので無理そう。。
var lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');
// map を作る
var row = 0
var col = 0
var map = []
for (const key in lines) {
const cells = lines[key].split(' ').map(cell => parseInt(cell))
if (key == 0) {
[col, row] = cells
} else if (key <= row) {
map.push(cells)
}
}
// 左上からカーソルを進めて、島をカウントしていく
var islandNo = 0
for (let r = 0; r < row; r++) {
for (let c = 0; c < col; c++) {
// セルが島であれば判定を開始する
if (map[r][c]) {
// 自身を新規の島にする
map[r][c] = 0
islandNo ++
// 4方向を確認して新規の島を探す
var stack = [[r, c]]
while (stack.length > 0) {
const [sr, sc] = stack.shift()
if (sr-1 >= 0 && map[sr-1][sc]) {
// 上方向に島があったら染めて再チェック
map[sr-1][sc] = 0
stack.push([sr-1, sc])
}
if (sc-1 >= 0 && map[sr][sc-1]) {
// 左方向に島があったら染めて再チェック
map[sr][sc-1] = 0
stack.push([sr, sc-1])
}
if (sr+1 < row && map[sr+1][sc]) {
// 下方向に島があったら染めて再チェック
map[sr+1][sc] = 0
stack.push([sr+1, sc])
}
if (sc+1 < col && map[sr][sc+1]) {
// 右方向に島があったら染めて再チェック
map[sr][sc+1] = 0
stack.push([sr, sc+1])
}
}
}
}
}
console.log(islandNo)
まとめ
これ以上は読みにくくなるから、私の感性ではこれで完成。
たまにはアルゴリズムの特訓良いよね。
でも実務ではあまり役に立たない悲しさ。。。