Submission

Score: 100

User: achinhchin

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

Language: cpp

Time: 0.053 second

Submitted On: 2026-02-25 20:13:54

#include <climits>
#include<iostream>
#include<utility>
#include<queue>
#define f first
#define s second
#define fr front
using namespace std;
typedef long long l;
l n,m,i,j,k,t,a,b,D[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,1},{-1,0},{-1,-1}},mn=LONG_LONG_MAX;
queue<pair<l,pair<l,l>>>Q;
pair<l,pair<l,l>>T;
bool A[1002][1002];
int main(){
  cin.tie(nullptr)->sync_with_stdio(0);
  cin>>n>>m;
  for(i=1;i<=n;i++)for(j=1;j<=m;j++){
    cin>>t;
    if(!t){
      A[i][j]=1;
      for(auto k:D)A[i+k[0]][j+k[1]]=1;
    }
  }for(i=1;i<=n;i++)if(!A[i][1])Q.push({1,{i,1}});
  while(!Q.empty()){
    if(!A[a=Q.fr().s.f][b=Q.fr().s.s]){
      A[Q.fr().s.f][b=Q.fr().s.s]=1;
      /*cout<<"==============\n";
      cout<<Q.fr().f<<' '<<a<<' '<<b<<'\n';
      for(i=0;i<=n+1;i++){
        for(j=0;j<=m+1;j++)cout<<A[i][j]<<' ';
        cout<<'\n';
      }*/
      if(b==m)mn=min(Q.fr().f,mn);
      for(i=0;i<8;i+=2)
        if(!A[a+D[i][0]][b+D[i][1]]&&a>=1&&b>=1&&a<=n&&b<m)
          Q.push({Q.fr().f+1,{a+D[i][0],b+D[i][1]}});
    }Q.pop();
  }cout<<(mn<LONG_LONG_MAX?mn:-1);
}