Submission

Score: 100

User: Bune

Problemset: ย่องเบาหลบกับระเบิด

Language: cpp

Time: 0.051 second

Submitted On: 2026-03-24 21:22:02

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

int main() {
  fastio

  int n, m;
  cin >> n >> m;

  vector<vector<int>> v(n + 5,vector<int>(m + 5));

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> v[i][j];
    }
  }

  vector<vector<bool>> vis(n + 5, vector<bool>(m + 5, false));

  vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
  vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (v[i][j] == 0) {
        vis[i][j] = true;
        for (int k = 0; k < 8; k++) {
          vis[i + dx[k]][j + dy[k]] = true;
        }
      }
    }
  }
  
  int iMx = 1e9;

  queue<pair<int, int>> q;
  vector<vector<int>> dis(n + 5, vector<int>(m + 5, iMx));

  for (int i = 1; i <= n; i++) {
    if (vis[i][1] == false) {
      q.push({i, 1});
      vis[i][1] = true;
      dis[i][1] = 1;
    }
  }

  vector<int> dxx = {0, 1, 0, -1};
  vector<int> dyy = {-1, 0, 1, 0};

  
  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    
    for (int i = 0; i < 4; i++) {
      int xx = x + dxx[i];
      int yy = y + dyy[i];

      if (xx < 1 && yy < 1 && xx > n && yy > m) {
        continue;
      }
      if (!vis[xx][yy] && v[xx][yy] == 1) {
        vis[xx][yy] = true;
        q.push({xx, yy});
        dis[xx][yy] = dis[x][y] + 1;
      }
    }
  }

  int mn = 1e9;
  for (int i = 1; i <= n; i++) {
    mn = min(mn, dis[i][m]);
  }

  if (mn == 1e9) {
    cout << "-1\n";
  }
  else {
    cout << mn << "\n";
  }

  return 0;
}