// https://www.geeksforgeeks.org/shortest-path-in-a-binary-maze/ #include using namespace std; const int Infini = numeric_limits::max(); // Type pour une cellule et sa plus courte distance struct node_t { pair point; // coordonnées d'une cellule int distance; // sa distance depuis la cellule source }; // "Breadth First Search" (BFS) int bfs(vector> &a) { // tableau des directions cardinales (N, O, E, S) // These arrays are used to get row and column numbers of 4 neighbours of a given cell int rowNum[] = { -1, 0, 0, 1 }; int colNum[] = { 0, -1, 1, 0 }; int m = a.size(), n = a[0].size(); // si la cellule source et/ou destination est bloquée, rien à faire if(!a[0][0] || !a[m-1][n-1]) return Infini; // tableau des cellules [non] visitées auto visited = vector>(m, vector(n, false)); visited[0][0] = true; // file d'attente (queue) pour BFS queue q; // la distance de la cellule source est 0 node_t s = {{0, 0}, 0}; q.push(s); // enfiler la cellule source // on commence une BFS à partir de la cellule source while(!q.empty()) { node_t curr = q.front(); // si on est arrivé à la cellule destination if(curr.point.first == m - 1 && curr.point.second == n - 1) return curr.distance; // sinon on défile la cellule et on enfile ses (4) cellules adjacentes q.pop(); for(int i = 0; i < 4; i++) // N, O, E, S { int row = curr.point.first + rowNum[i]; int col = curr.point.second + colNum[i]; // si la cellule adjacente est valide et pas encore visitée if(row >= 0 && row < m && col >= 0 && col < n && a[row][col] && !visited[row][col]) { // marquer la cellule comme visitée et l'enfiler visited[row][col] = true; node_t Adjcell = {{row, col}, curr.distance + 1}; q.push(Adjcell); } } } return Infini; } // bfs() int main() { int m, n; cin >> m >> n; auto a = vector>(m, vector(n)); for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) cin >> a[i][j]; auto d = bfs(a); if(d == Infini) cout << "Impossible" << endl; else cout << d << endl; return 0; } // main()