iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 3
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 3

Day3-二維陣列與數地雷應用

這次要來介紹的是二維陣列,二維陣列就是陣列裡面的元素也是陣列的一種資料結構
舉個例子來說:

const group = [
  ['172', '156', '182'],
  ['172', '156', '182']
];
console.log(group[0]); // ['172', '156', '182']
console.log(group[1]); // ['172', '156', '182']

以上這就是二維陣列,當然還有三維陣列,四維陣列等...在此不再多述。接下來我們來實際使用二維陣列來解決一個問題吧!

問題描述:

相信大家都有玩過踩地雷吧!

那此問題就是要將一個二維陣列中的地雷和非地雷的數字依據橫直行一行一行的顯示出來,實際的輸出輸入如下:

一個地雷區域

const minefield = [
  ['', '*', '', '*'],
  ['*', '*', '', '*'],
  ['', '', '*', ''],
  ['', '', '', ''],
];

印出地雷和周圍地雷總數的數字

// 3*4*
// **5*
// 23*2
// 0111

那麼要怎麼解決此問題呢?我們可以這樣思考:

  1. 一定要對陣列內每個元素進行遍歷
  2. 假如遍歷到的元素是地雷,就讓它加入到要輸出的字串
  3. 假如遍歷到的元素是數字,就必須針對它周圍的八個方向進行判斷是否是地雷,是的話該元素就+1
  4. 但是有些元素並沒有八個方向都是數字或是地雷,因此要對這些狀況進行額外判斷
  5. 經過以上內容考量後就能順利將結果打印出來了,我們就來用程式實作吧!

首先我們有了這樣的陣列:

const minefield = [
  ['', '*', '', '*'],
  ['*', '*', '', '*'],
  ['', '', '*', ''],
  ['', '', '', ''],
];

先透過雙重迴圈進行遍歷,判斷是否遍歷到的元素為地雷,是的話就加入字串

function minesweeper(minefield) {
  // 此層迴圈為第一層陣列
  for (let i = 0; i < minefield.length; i++) {
    let string = '';
    // 此層迴圈為第一層陣列內的每個元素內的陣列
    for (let j = 0; j < minefield[i].length; j++) {
      // 假如某點是*,直接印出來
      // 假如不是,去計算九宮格內有幾個*
      if (minefield[i][j] == '*') {
        string += minefield[i][j];
      } else {

      }
    }
  console.log(string);
  }
}

minesweeper(minefield);

此時輸出字串的話會長這樣:

**
***
*

接著要計算每個非地雷元素的周圍有幾個地雷,那麼要怎麼取出元素周圍八個方向的元素值做判斷呢?我們看這張圖

由上而下的直欄位由 i 控制,因此在中心點元素,也就是遍歷的元素,往上一橫欄就是i-1,往下一橫欄就是i+1
由左而右的橫欄位由 j 控制,往左一直欄就是j-1,往右一直欄就是j+1

這時主程式可以寫一些想法在 else{} 內:

function minesweeper(minefield) {
  // 此層迴圈為第一層陣列
  for (let i = 0; i < minefield.length; i++) {
    let string = '';
    // 此層迴圈為第一層陣列內的每個元素內的陣列
    for (let j = 0; j < minefield[i].length; j++) {
      // 假如某點是*,直接印出來
      // 假如不是,去計算九宮格內有幾個*
      if (minefield[i][j] == '*') {
        string += minefield[i][j];
      } else {
        // 初始設定為0個地雷
        let temp = 0;
        
        // minefield[i-1][j-1]是地雷就 temp++;
        // minefield[i-1][j]是地雷就 temp++;
        // minefield[i-1][j+1]是地雷就 temp++;
        // minefield[i][j-1]是地雷就 temp++;
        // minefield[i][j+1]是地雷就 temp++;
        // minefield[i+1][j-1]是地雷就 temp++;
        // minefield[i+1][j]是地雷就 temp++;
        // minefield[i+1][j+1]是地雷就 temp++;
        
        string += temp;
      }
    }
  console.log(string);
  }
}

minesweeper(minefield);

因此只要將每個方向的元素做判斷是否為地雷,如果是的話就+1
最後將temp加入字串就可以輸出結果了...No!別忘了
並不是每個元素的八個方向都有別的元素存在啊/images/emoticon/emoticon15.gif

因此我們要設定一個函式去做判斷:
i: 元素的直欄位索引
j: 元素的橫欄位索引

function changeField(i, j) {
  // i 和 j 的值小於0時,不會有任何元素存在
  if (i < 0 || j < 0) {
    return 0;
  } else if (i >= minefield.length) {
    // 超過直欄位總數的長度,也沒有元素存在
    return 0;
  } else if (j >= minefield[i].length) {
    // 超過直欄位總數的長度,也沒有元素存在
    return 0;
  } else if (minefield[i][j] == '*') {
    // 假如查找的元素是地雷,就回傳1(代表一個地雷,之後可以呼叫changeField(i, j)來做地雷個數加總)
    return 1;
  } else {
    // 如果確實有元素存在但不是地雷的話,也是回傳0
    return 0;
  }
}

有這個函式後,我們將minesweeper()這隻函式改寫成這樣:

function minesweeper(minefield) {
  // 此層迴圈為第一層陣列
  for (let i = 0; i < minefield.length; i++) {
    let string = '';
    // 此層迴圈為第一層陣列內的每個元素內的陣列
    for (let j = 0; j < minefield[i].length; j++) {
      // 假如某點是*,直接印出來
      // 假如不是,去計算九宮格內有幾個*
      if (minefield[i][j] == '*') {
        string += minefield[i][j];
      } else {
        let temp = 0;
        temp += changeField(i - 1, j - 1); // 左上
        temp += changeField(i - 1, j); // 正上
        temp += changeField(i - 1, j + 1); // 右上
        temp += changeField(i, j - 1); // 左中
        temp += changeField(i, j + 1); // 右中
        temp += changeField(i + 1, j - 1); // 左下
        temp += changeField(i + 1, j); // 正下
        temp += changeField(i + 1, j + 1); // 右下
        string += temp;
      }
    }
  console.log(string);
  }
}

minesweeper(minefield);

我們藉由changeField()函式的回傳值算出地雷數了!
最後結果如下:

// 3*4*
// **5*
// 23*2
// 0111

恭喜解決這個問題,下面連結是完整的程式碼
https://github.com/a90100/javascript-data-structure/blob/master/day3-array.js


明天我們將進入鏈結串列來做介紹,敬請期待!/images/emoticon/emoticon07.gif


上一篇
Day2-陣列操作常用的20個函式
下一篇
Day4-來了解鏈結串列(Linked List)並實作它吧!
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言