Submission

Score: 100

User: Poon

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

Language: cpp

Time: 0.106 second

Submitted On: 2026-03-14 00:12:24

#include <bits/stdc++.h>
using namespace std;

int main() 
{
  int n,m;
  cin>>n>>m;
  vector<vector<bool>> grid(n,vector<bool>(m));
  vector<pair<int,int>> bomb;
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<m;j++)
    {
      int x;
      cin>>x;
      grid[i][j]=bool(x);
      if(!grid[i][j]) bomb.push_back({i,j});
    }
  }
  int x[]={0,0,1,1,1,-1,-1,-1};
  int y[]={1,-1,0,1,-1,0,1,-1};
  for(auto &[a,b] : bomb)
  {
    for(int k=0;k<8;k++)
    {
      int i=a+x[k],j=b+y[k];
      if(i>=0&&j>=0&&i<n&&j<m)
      {
        grid[i][j]=false;
      }
    }
  }
  queue<pair<int,int>> q;
  vector<vector<int>> visited(n,vector<int>(m,1e9));
  for(int i=0,j=0;i<n;i++)
  {
    if(grid[i][j])
    {
      q.push({i,j});
      visited[i][j]=0;
    }
  }
  int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
  while(!q.empty())
  {
    int i=q.front().first,j=q.front().second;
    q.pop();
    for(int k=0;k<4;k++)
    {
      int ii=i+dx[k],jj=j+dy[k];
      if(ii>=0&&jj>=0&&ii<n&&jj<m&&visited[ii][jj]==1e9&&grid[ii][jj])
      {
        q.push({ii,jj});
        visited[ii][jj]=visited[i][j]+1;
      }
    }
  }
  int minn=1e9;
  for(int i=0,j=m-1;i<n;i++)
  {
    minn=min(minn,visited[i][j]);
  }
  if(minn==1e9)
  {
    cout<<"-1";
  }
  else
  {
    cout<<minn+1;
  }
}