Submission

Score: 0

User: Quaoar

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-01-01 16:30:22

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;

int n,m;
vector<vector<int>> map;

int bfs(vector<vector<int>> &map){
    int dx[] = {-1,1,0,0};
    int dy[] = {0,0,-1,1};

    queue<tuple<int,int,int>> q;

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    for (int i = 0 ; i < n ; i++){
        if (map[i][0] == 1){
            q.push({i, 0, 0});
            visited[i][0] = true;
        }
    }

    while (!q.empty())
    {
        tuple <int,int,int> t = q.front();
        int x = get<0>(t);
        int y = get<1>(t);
        int len = get<2>(t);
        q.pop();

        if (y == m - 1){
            return len;
        }

        for (int i = 0 ; i < 4 ; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
        

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && map[nx][ny] == 1){
                visited[nx][ny] = true;
                q.push({nx,ny,len + 1});
            }
        }
    }
    return -1;  
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0 ; i < n ; i++){
        vector<int> row;
        for (int j = 0 ; j < m ; j++){ 
            int temp;
            cin >> temp;
            row.push_back(temp);
        }
        map.push_back(row);
    }
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < m ; j++){
            if (map[i][j] == 0){

                for (int nx = -1 ; nx <= 1 ; nx++){
                    for (int ny = -1 ; ny <= 1 ; ny++){
                        if (nx + i < n && nx + i >= 0){
                            if (ny + j < m && ny + j >= 0 && map[nx + i][ny + j] != 0) map[nx + i][ny + j] = 2;
                        }
                    }
                }
                
            }
        }
    }
    
    cout << "\n";
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < m ; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    
    if (bfs(map) == -1){
        cout << -1;
    } else {
        cout << bfs(map) + 1;
    }
    return 0;
}