希望藉由程式解題的過程重新打好程式基礎和學習遺漏的相關知識點
會將解題過程遇到困難的地方做個紀錄
測驗網站：LidemyOJ ( LIOJ ) by 胡立 ( Huli )
免費課程 — [ALG101] 先別急著寫 leetcode by 胡立 ( Huli )
討論區：Lidemy Discussions by 胡立 ( Huli )
🔖 文章索引
1. 初次解題想法
2. 參考文章
3. Do ... While
4. Recursion
5. 補充相關知識
6. 延伸閱讀初次解題想法
看到 Sample Input 以為這題很簡單只要將 . 全部計算出來減 1 就是答案
# Sample Input
6 5
.#####
.#####
.#####
.#####
......
# Sample Output
9後來在討論區看到老師提供的測資就發現這題不簡單
# Sample Input
3 3
.#.
.#.
...
# Sample Output
4# Sample Input
18 9
...##########....#
##........###.##.#
#########.###.##.#
...#...##.###.##.#
.#.#.#.##.###.##.#
.#...#....###.##.#
.############.##.#
..............##.#
################..
# Sample Output
65參考文章
從文章中可以理解到這一題題目可以用 深度優先搜尋演算法 ( Depth-First-Search，DFS ) 來解題
題目描述中有提到［保證中間不會有任何岔路］［每一個迷宮保證只會有唯一一種走法］［起點永遠在左上角］［終點永遠在右下角］
解題想法從［0, 0］往四周探索遇到 . 就接續往四周探索並記錄已經探索過的位置一直到終點為止
Note: 將迷宮轉換成 矩陣 後 x 的邊界是 height 而 y 的邊界是 width
Do … While
var readline = require('readline');
var lines = []
var rl = readline.createInterface({
input: process.stdin
});
rl.on('line', function (line) {
lines.push(line)
});
rl.on('close', function() {
solve(lines)
})
const log = console.log;
const matrix = [];
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // 右、左、上、下
let visited = null;
const answer = [];
let width = 0;
let height = 0;
function solve(lines) {
const temp = lines[0].split(' ').map((item) => Number(item));
width = temp[0];
height = temp[1];
visited = new Array(height).fill('').map(() => new Array(width).fill(false));
for (let i = 1; i <= height; i++) {
matrix.push(lines[i].split(''));
}
let currentRow = 0;
let currentColumn = 0;
let isFinal = false;
visited[currentRow][currentColumn] = true;
do {
for (let dir of dirs) {
let nextX = currentRow + dir[0];
let nextY = currentColumn + dir[1];
if (
nextX < height &&
nextX >= 0 &&
nextY < width &&
nextY >= 0 &&
matrix[nextX][nextY] === '.' &&
visited[nextX][nextY] === false
) {
visited[nextX][nextY] = true;
let temp = [];
temp.push(nextX, nextY)
answer.push(temp);
currentRow = nextX;
currentColumn = nextY;
if (currentRow === height - 1 && currentColumn === width - 1) {
isFinal = true;
break;
}
}
}
} while (!isFinal);
log(answer.length);
}Recursion
var readline = require('readline');
var lines = []
var rl = readline.createInterface({
input: process.stdin
});
rl.on('line', function (line) {
lines.push(line)
});
rl.on('close', function() {
solve(lines)
})
const log = console.log;
const matrix = [];
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // 右、左、上、下
let visited = null;
const answer = [];
let width = 0;
let height = 0;
function solve(lines) {
const temp = lines[0].split(' ').map((item) => Number(item));
width = temp[0];
height = temp[1];
visited = new Array(height).fill('').map(() => new Array(width).fill(false));
for (let i = 1; i <= height; i++) {
matrix.push(lines[i].split(''));
}
dfs(0, 0);
visited[0][0] = true;
}
function dfs(x, y) {
if (x === height - 1 && y === width - 1) {
log(answer.length);
return;
}
for (let dir of dirs) {
let nextX = x + dir[0];
let nextY = y + dir[1];
if (
nextX < height &&
nextX >= 0 &&
nextY < width &&
nextY >= 0 &&
matrix[nextX][nextY] === '.' && // "." => Road, "#" => Wall
visited[nextX][nextY] === false
) {
visited[nextX][nextY] = true;
let temp = [];
temp.push(nextX, nextY)
answer.push(temp);
dfs(nextX, nextY);
}
}
}
