Submission

Score: 0

User: ttttttttt

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

Language: cpp

Time: 0.000 second

Submitted On: 2025-12-07 14:37:17

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

void bomb(vector<vector<int>> arr, int x, int y)
{
    vector<pair<int>> idx = {{x+1,y}, {x-1,y}, {x,y+1},{x,y-1},
                            {x+1,y+1},{x+1,y-1},{x-1,y+1},{x-1,y-1}
                            }
    for(int i = 0; i < idx.size();i++)
    {
        int xx = idx.first;
        int yy = idx.second;
        if(xx<0 || xx>=arr[0].size()) continue;
        if(yy<0 || yy>=arr.size()) continue;
        arr[xx][yy] = 0;
    }
}

void dist(vector<vector<int>> arr, int x, int, y, int dist, queue<pair<int,int>> idx)
{
    vector<pair<int>> idx = {{x+1,y}, {x-1,y}, {x,y+1},{x,y-1},
                            {x+1,y+1},{x+1,y-1},{x-1,y+1},{x-1,y-1}
                            }
    for(int i = 0; i < idx.size();i++)
    {
        int xx = idx.first;
        int yy = idx.second;
        if(xx<0 || xx>=arr[0].size()) continue;
        if(yy<0 || yy>=arr.size()) continue;
        if(!visited[xx][yy])
        {
            if(arr[xx][yy] != 0) dist[xx][yy] = dist+1;
            visited[xx][yy] = true;
            idx.push({xx,yy});
        }
    }
}

int main()
{
    int n, m; cin>>n>>m;
    vector<vector<int>> arr(n, vector<int>(m, 1));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin>>arr[i][j];
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(arr[i][j] == 0) bomb(arr, i, j);
        }
    }
    
    queue<pair<int,int>> idx;
    for(int i = 0; i < n; i++)
    {
        idx.push({0,i});
    }
    
    vector<vector<int>> dist(n, vector<int>(m,INT_MAX));
    vector<vector<Int>> visited(n, vector<int>(m, false));
    
    for(int i = 0; i<n; i++)
    {
        dist[i][0] = 0;
        visited[i][0] = true;
    }
    
    while(!idx.empty())
    {
        int x = idx.front().first;
        int y = idx.front().second;
        idx.pop();
        dist(dist, x, y, dist[x][y], idx, visited);
    }
    int ans = INT_MAX;
    for(int i = 0; i < n; i++)
    {
        ans = min(ans, dist[i][m-1]);
    }
    cout<<(ans == INT_MAX ? -1 : ans)<<endl;
}