Submission

Score: 100

User: Ninstroyer

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

Language: cpp

Time: 0.114 second

Submitted On: 2025-12-17 20:15:01

#include <bits/stdc++.h>
using namespace std;
const int nx = 1e3+5;

vector<pair<int,int>> dir = {{0,-1}, {0,1}, {1,0}, {-1, 0}, {-1, 1}, {-1,-1}, {1,-1}, {1,1}};

int main()
{
    int n, m; cin>>n>>m;
    vector<vector<int>> arr(nx, vector<int>(nx));
    vector<vector<int>> marked(nx, vector<int>(nx, 0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>arr[i][j];
            if(arr[i][j] == 0) marked[i][j] = 1;
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(marked[i][j])
            {
                for(int k = 0; k < 8; k++)
                {
                    auto [x,y] = dir[k];
                    arr[i+x][j+y] = 0;
                }
            }
        }
    }

    queue<pair<int,int>> q;
    vector<vector<int>> dist(nx, vector<int>(nx, 1e9+5));
    vector<vector<bool>> visited(nx, vector<bool>(nx, false));
    for(int i = 1; i <= n; i++)
    {
        if(arr[i][1] != 0) q.push({i, 1});
        else continue;
        dist[i][1] = 1;
        visited[i][1] = true;
    }
    while(!q.empty())
    {
        auto [i,j] = q.front();
        q.pop();
        for(int k = 0; k < 4; k++)
        {
            auto [x,y] = dir[k];
            int ni = i+x;
            int nj = j+y;
            if(ni > n || ni < 1 || nj > m || nj < 1) continue;
            if(arr[ni][nj] && !visited[ni][nj])
            {
                dist[ni][nj] = dist[i][j] + 1;
                q.push({ni, nj});
                visited[ni][nj] = true;
            }
        }
    }

    int ans = 1e9+5;
    for(int i = 1; i <= n; i++)
    {
        ans = min(ans, dist[i][m]);
    }
    cout<<(ans == 1e9+5 ? -1 : ans);
}