Submission

Score: 100

User: erng

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

Language: cpp

Time: 0.052 second

Submitted On: 2025-11-23 14:46:18

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

int n, m, mp[1005][1005], di[8]={1, 1, 0, -1, -1, -1, 0, 1}, dj[8]={0, 1, 1, 1, 0, -1, -1, -1}, vs[1005][1005], dist[1005][1005];
queue<pair<int,int>> q;
int ni[4]={0, 1, 0, -1}, nj[4]={-1, 0, 1, 0}, mn=INT_MAX;
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cin>>mp[i][j];
        }
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (!mp[i][j])
            {
                for (int k=0; k<8; k++)
                {
                    int ci=i+di[k], cj=j+dj[k];
                    if (mp[ci][cj]==0) continue;
                    mp[ci][cj]=2;
                }
            }
        }
    }
    for (int i=1; i<=n; i++)
    {
        if (mp[i][1]!=1) continue;
        // cout<<"push "<<i<<' '<<1<<'\n';
        q.push({i, 1});
        vs[i][1]=1;
    }
    while(!q.empty())
    {
        auto [i, j]=q.front();
        q.pop();
        // cout<<"i "<<i<<' '<<j<<'\n'; 
        for (int k=0; k<4; k++)
        {
            int ci=i+ni[k], cj=j+nj[k];
            // cout<<"ci "<<ci<<' '<<cj<<' '<<vs[ci][cj]<<' '<<mp[ci][cj]<<'\n';
            if (vs[ci][cj]==1 || mp[ci][cj]!=1) continue;
            vs[ci][cj]=1;
            dist[ci][cj]=dist[i][j]+1;
            q.push({ci, cj});
        }
    }
    for (int i=1; i<=n; i++)
    {
        if (dist[i][m]==0) continue;
        mn=min(mn, dist[i][m]);
    }
    if (mn==INT_MAX) cout<<-1;
    else cout<<mn+1;
}