はじめに

---

行列(Matrix)がstd::vector<std::vector<int>>で与えられ，各要素から一番近い0までの距離を格納した行列を算出する問題．

今回は，BFS 的な解法を作ってみた．

コード全体

---

class Solution {
  bool withinRange(vector<vector<int>> const& mat, int i, int j) {
    if (i < 0) return false;
    if (j < 0) return false;
    if (mat.size() <= i) return false;
    if (mat[0].size() <= j) return false;
    return true;
  }

public:
  vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {

    vector<vector<int>> distances(mat.size(), vector<int>(mat[0].size(), -1));
    queue<pair<int,int>> q;
    for (int i=0; i<mat.size(); ++i) {
      for (int j=0; j<mat[i].size(); ++j) {
        if (mat[i][j] == 0) {
          distances[i][j] = 0;
          if (withinRange(mat, i-1, j) && mat[i-1][j] != 0) q.emplace(i-1, j);
          if (withinRange(mat, i+1, j) && mat[i+1][j] != 0) q.emplace(i+1, j);
          if (withinRange(mat, i, j-1) && mat[i][j-1] != 0) q.emplace(i, j-1);
          if (withinRange(mat, i, j+1) && mat[i][j+1] != 0) q.emplace(i, j+1);
        }
      }
    }

    int distance = 1;
    int i, j;
    while(!q.empty()) {
      int n = q.size();
      while (n) {
        tie(i, j) = q.front();
        if (distances[i][j] < 0) distances[i][j] = distance;

        if (withinRange(distances, i-1, j) && distances[i-1][j] < 0) q.emplace(i-1, j);
        if (withinRange(distances, i+1, j) && distances[i+1][j] < 0) q.emplace(i+1, j);
        if (withinRange(distances, i, j-1) && distances[i][j-1] < 0) q.emplace(i, j-1);
        if (withinRange(distances, i, j+1) && distances[i][j+1] < 0) q.emplace(i, j+1);

        n--;
        q.pop();
      }
      distance++;
    }

    return distances;
  }
};

解説

---

クラス定義

---

class Solution {

補助関数

---

暗黙的にプライベートメソッドとして定義．

これは，コード簡略化のために定義しており，matに対して２つのインデックスi, jが範囲内かどうかを戻す．

  bool withinRange(vector<vector<int>> const& mat, int i, int j) {
    if (i < 0) return false;
    if (j < 0) return false;
    if (mat.size() <= i) return false;
    if (mat[0].size() <= j) return false;
    return true;
  }

関数

---

distancesは，題意を満たすvector<vector>>を格納するための配列．

初期値を-1としているが，これは未探索を意味する事にした．つまり，探索済みの要素はdistances[i][j]の値が0以上になるということである．

public:
  vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {

    vector<vector<int>> distances(mat.size(), vector<int>(mat[0].size(), -1));

キューの準備

---

qには，未探索の要素番号を順次格納する．

初期状態は，mat[i][j]が0である{i, j}をすべて詰め込む．

    queue<pair<int,int>> q;
    for (int i=0; i<mat.size(); ++i) {
      for (int j=0; j<mat[i].size(); ++j) {
        if (mat[i][j] == 0) {
          distances[i][j] = 0;
          if (withinRange(mat, i-1, j) && mat[i-1][j] != 0) q.emplace(i-1, j);
          if (withinRange(mat, i+1, j) && mat[i+1][j] != 0) q.emplace(i+1, j);
          if (withinRange(mat, i, j-1) && mat[i][j-1] != 0) q.emplace(i, j-1);
          if (withinRange(mat, i, j+1) && mat[i][j+1] != 0) q.emplace(i, j+1);
        }
      }
    }

ループの準備

---

distanceは，上で準備したqの0までの距離を意味する．最初にqに入っている位置は，距離が0となる．

i, jはループ内で，インデックスとして利用する．

    int distance = 1;
    int i, j;

ループ

---

すべての要素が探索終了するまで繰り返す．

    while(!q.empty()) {

キュー内の距離を記録

---

現在のqのサイズを残しておくのは，距離の記録と共に，次の探索点もキューにプッシュしてくためである．

tieでqの先頭を受け取り，その位置が未探索であれば，距離distanceを保存．

また，その位置の左右上下がmatの範囲内でかつ未探索であれば，次の探索点としてqにプッシュする．

      int n = q.size();
      while (n) {
        tie(i, j) = q.front();
        if (distances[i][j] < 0) distances[i][j] = distance;

        if (withinRange(distances, i-1, j) && distances[i-1][j] < 0) q.emplace(i-1, j);
        if (withinRange(distances, i+1, j) && distances[i+1][j] < 0) q.emplace(i+1, j);
        if (withinRange(distances, i, j-1) && distances[i][j-1] < 0) q.emplace(i, j-1);
        if (withinRange(distances, i, j+1) && distances[i][j+1] < 0) q.emplace(i, j+1);

        n--;
        q.pop();
      }

距離を更新

---

      distance++;
    }

戻り値

---

    return distances;
  }
};

おわりに

---

私の解答は，コンパクトにまとまっているコードではないため，Discussion も参考に居てもらえたらと思います．

参考

---

• https://leetcode.com/problems/01-matrix