# APCS 20190615 P2 機器人走棋盤
###### tags: `APCS`

## 題目大意
有一個 $m \times n$ 的方格棋盤，
（有 $m$ 個橫行（row）、$n$ 個直行（column））
每一格上面都有一個數字，
機器人會選數字最小的格子作為起點，
接下來每一步會往上下左右數字最小的格子走，
並且它不會走重複的路，也不會走出邊界，
它會一直走到不能走為止，求它經過的所有數字的總和。

輸入第一行有兩個正整數 $m$ 和 $n$，
接下來有 $m$ 行，每行有 $n$ 個數字，表示棋盤各個格子的數字。

輸出機器人經過的所有數字的總和。

$1 \leq m, n \leq 100$
棋盤的每個數字不超過 $100,000$

## 解法
一開始要找數字最小的格子，
就在讀取輸入時一邊記錄最小的格子就好。

接下來有一個小技巧，機器人有四個方向可以選，
所以可以開一個二維陣列，裡面儲存往每個方向走，座標會加減多少，
如以下 code 第 5 行。

因為不能走重複的路，所以開一個二維陣列來記錄走過的格子，
（記得初始化，下面用 vector 的原因是這樣會自動全部初始化成 false）
接下來要判斷要走哪個格子，
只要利用剛剛的小技巧，就可以很輕鬆地找到每一個可以選的格子，
並且判斷那格走過了沒，一邊記錄最小的格子是哪格。
（見以下 code 第 36 到 48 行）

## Code

#include <bits/stdc++.h>

using namespace std;

int direction[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int m, n;
    cin >> m >> n;

    int table[m][n];
    int nowy = 0;
    int nowx = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> table[i][j];
            if(table[nowy][nowx] > table[i][j]){
                nowy = i;
                nowx = j;
            }
        }
    }

    int ans = 0;
    vector<vector<bool>> book(m, vector<bool>(n));
    book[nowy][nowx] = true;
    ans += table[nowy][nowx];
    while(true){
        int miny = -1;
        int minx = -1;
        for(int i = 0; i < 4; i++){
            int newy = nowy + direction[i][0];
            int newx = nowx + direction[i][1];
            if(newy < 0 || newy >= m || newx < 0 || newx >= n){
                continue;
            }
            if(book[newy][newx]){
                continue;
            }
            if(miny == -1 || table[newy][newx] < table[miny][minx]){
                miny = newy;
                minx = newx;
            }
        }
        if(miny == -1){
            break;
        }
        nowy = miny;
        nowx = minx;
        ans += table[nowy][nowx];
        book[nowy][nowx] = true;
    }
    cout << ans << "\n";

    return 0;
}