Submission

Score: 100

User: nadfd

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

Language: cpp

Time: 0.142 second

Submitted On: 2025-12-07 17:06:23

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> field(n+2, vector<int> (m+2, 2));
    vector<vector<int>> vs(n+2, vector<int> (m+2, 0));
    vector<vector<int>> dist(n+2, vector<int> (m+2, 1e9));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> field[i][j];

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
    if(field[i][j] == 0){
        if(field[i-1][j] != 0) field[i-1][j] = 2;
        if(field[i-1][j-1] != 0) field[i-1][j-1] = 2;
        if(field[i-1][j+1] != 0) field[i-1][j+1] = 2;
        if(field[i][j-1] != 0) field[i][j-1] = 2;
        if(field[i][j+1] != 0) field[i][j+1] = 2;
        if(field[i+1][j] != 0) field[i+1][j] = 2;
        if(field[i+1][j-1] != 0) field[i+1][j-1] = 2;
        if(field[i+1][j+1] != 0) field[i+1][j+1] = 2;
    }
    queue<pair<int, int>> q;
    for(int j = 1; j <= n; j++)
        if(field[j][1]%2 != 0){
            q.push({j, 1});
            dist[j][1]=0;
            vs[j][1] = 1;
        }
    while(!q.empty()){
        auto [cx, cy] = q.front();
        q.pop();
        if(!vs[cx+1][cy] && field[cx+1][cy]%2){
            vs[cx+1][cy] = 1;
            dist[cx+1][cy] = dist[cx][cy]+1;
            q.push({cx+1, cy});
        }
        if(!vs[cx-1][cy] && field[cx-1][cy]%2){
            vs[cx-1][cy] = 1;
            dist[cx-1][cy] = dist[cx][cy]+1;
            q.push({cx-1, cy});
        }
        if(!vs[cx][cy-1] && field[cx][cy-1]%2){
            vs[cx][cy-1] = 1;
            dist[cx][cy-1] = dist[cx][cy]+1;
            q.push({cx, cy-1});
        }
        if(!vs[cx][cy+1] && field[cx][cy+1]%2){
            vs[cx][cy+1] = 1;
            dist[cx][cy+1] = dist[cx][cy]+1;
            q.push({cx, cy+1});
        }
    }
    long long mn = 1e9;
    for(int j = 1; j <= n; j++)
        if(field[j][m]%2 != 0 && dist[j][m] < mn)
            mn = dist[j][m];
    if(mn == 1e9)
        cout << -1;
    else
        cout << mn+1;
    return 0;
}