Caminos más cortos con aristas no ponderadas

#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
#define pb push_back
 
int main() {
	int N, M;
	cin >> N >> M;
	vi dist(N + 1, INT_MAX), parent(N + 1);
	vector<vi> adj(N + 1);
	while (M--) {
		int a, b;
		cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	queue<int> q;
	dist[1] = 0;
	q.push(1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int t : adj[x])
			if (dist[t] == INT_MAX) {
				dist[t] = dist[x] + 1;
				parent[t] = x;
				q.push(t);
			}
	}
	if (dist[N] == INT_MAX) cout << "IMPOSSIBLE";
	else {
		cout << dist[N] + 1 << "\n";
		vi v{N};
		while (v.back() != 1) v.pb(parent[v.back()]);
		reverse(begin(v), end(v));
		for (int t : v) cout << t << " ";
	}
}

import java.io.*;
import java.util.*;
 
public class Solution {
	// CodeSnip{Kattio}
 
	private static Map<Integer, LinkedList<Integer>> adj = new HashMap<>();
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt(), m = io.nextInt();
		for (int i = 0; i < m; i++) {
			int a = io.nextInt(), b = io.nextInt();
			if (adj.get(a) == null) { adj.put(a, new LinkedList<>()); }
 
			if (adj.get(b) == null) { adj.put(b, new LinkedList<>()); }
 
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		int[] prev = new int[n + 1], dist = new int[n + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1] = 1;
 
		Queue<Integer> bfs = new LinkedList<>();
		bfs.add(1);
 
		while (!bfs.isEmpty()) {
			int top = bfs.poll();
			if (dist[top] == Integer.MAX_VALUE) continue;
			if (adj.get(top) != null) {
				for (int e : adj.get(top)) {
					if (dist[e] == Integer.MAX_VALUE) {
						dist[e] = dist[top] + 1;
						prev[e] = top;
						bfs.add(e);
					}
				}
			}
		}
 
		if (dist[n] == Integer.MAX_VALUE) {
			System.out.println("IMPOSSIBLE");
		} else {
			System.out.println(dist[n]);
			int[] res = new int[dist[n]];
			int i = dist[n] - 1;
			for (int x = n; x != 0; x = prev[x]) { res[i--] = x; }
			for (int a : res) System.out.print(a + " ");
		}
	}
}

from collections import deque, defaultdict
 
n, m = map(int, input().split())
edges = []
for _ in range(m):
	a, b = map(int, input().split())
	edges.append((a, b))
 
graph = defaultdict(list)
for a, b in edges:
	graph[a].append(b)
	graph[b].append(a)
 
# Preparación del BFS
queue = deque([1])
distance = [-1] * (n + 1)
parent = [-1] * (n + 1)
distance[1] = 0
 
while queue:
	node = queue.popleft()
 
	for neighbor in graph[node]:
		if distance[neighbor] == -1:  # Si el vecino no fue visitado
			distance[neighbor] = distance[node] + 1
			parent[neighbor] = node
			queue.append(neighbor)
			if neighbor == n:  # Si llegamos al destino
				# Reconstruir el camino
				path = []
				current = n
				while current != -1:
					path.append(current)
					current = parent[current]
				path.reverse()
 
				print(len(path))
				print(" ".join(map(str, path)))
				exit()
 
# Si no se encontró camino
print("IMPOSSIBLE")

#include <bits/stdc++.h>
using namespace std;
 
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
 
int n, m, depth[4000][4000], ans = 1;
string snow[4000];
 
bool inside(int x, int y) {
	return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}
 
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
 
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> snow[i];
 
	deque<pair<int, int>> q;
	q.push_back({0, 0});
	depth[0][0] = 1;
 
	while (q.size()) {
		pair<int, int> c = q.front();
		q.pop_front();
		ans = max(ans, depth[c.first][c.second]);
 
		for (int i = 0; i < 4; i++) {
			int x = c.first + dx[i], y = c.second + dy[i];
			if (inside(x, y) && depth[x][y] == 0) {
				if (snow[x][y] == snow[c.first][c.second]) {
					depth[x][y] = depth[c.first][c.second];
					q.push_front({x, y});
				} else {
					depth[x][y] = depth[c.first][c.second] + 1;
					q.push_back({x, y});
				}
			}
		}
	}
 
	cout << ans;
	return 0;
}

import java.io.*;
import java.util.*;
 
public class tracks {
	static final int[] dx = {0, 0, -1, 1};
	static final int[] dy = {-1, 1, 0, 0};
	static int N = 1, H, W;
	static int[][] grid, count;
	public static void main(String[] args) {
		FastIO io = new FastIO();
 
		H = io.nextInt();
		W = io.nextInt();
		grid = new int[H][W];
 
		for (int i = 0; i < H; i++) {
			String line = io.next();
			for (int j = 0; j < W; j++) {
				grid[i][j] = (line.charAt(j) == 'F')   ? 1
				             : (line.charAt(j) == 'R') ? 2
				                                       : -1;
			}
		}
 
		io.println(bfs());
		io.close();
	}
 
	private static int bfs() {
		count = new int[H][W];
 
		LinkedList<int[]> q = new LinkedList<>();
		q.add(new int[] {0, 0});
		count[0][0] = 1;
 
		while (!q.isEmpty()) {
			int[] curr = q.poll();
 
			N = Math.max(N, count[curr[0]][curr[1]]);
 
			for (int i = 0; i < 4; i++) {
				int nx = curr[0] + dx[i];
				int ny = curr[1] + dy[i];
 
				if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
				if (count[nx][ny] > 0) continue;
				if (grid[nx][ny] == -1) continue;
				if (grid[nx][ny] != grid[curr[0]][curr[1]]) {
					count[nx][ny] = count[curr[0]][curr[1]] + 1;
					q.addLast(new int[] {nx, ny});
				} else {
					count[nx][ny] = count[curr[0]][curr[1]];
					q.addFirst(new int[] {nx, ny});
				}
			}
		}
 
		return N;
	}
 
	// BeginCodeSnip{FastIO}
	private static class FastIO extends PrintWriter {
		private InputStream stream;
		private byte[] buf = new byte[1 << 16];
		private int curChar, numChars;
 
		// entrada estándar
		public FastIO() { this(System.in, System.out); }
		public FastIO(InputStream i, OutputStream o) {
			super(o);
			stream = i;
		}
		// entrada por archivo
		public FastIO(String i, String o) throws IOException {
			super(new FileWriter(o));
			stream = new FileInputStream(i);
		}
 
		// lanza InputMismatchException() si se detectó previamente el fin de archivo
		private int nextByte() {
			if (numChars == -1) throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) { throw new InputMismatchException(); }
				if (numChars == -1) return -1;  // fin de archivo
			}
			return buf[curChar++];
		}
 
		// para leer líneas enteras, reemplazar c <= ' '
		// por una función que compruebe si c es un salto de línea
		public String next() {
			int c;
			do { c = nextByte(); } while (c <= ' ');
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = nextByte();
			} while (c > ' ');
			return res.toString();
		}
		public int nextInt() {  // nextLong() se implementaría de forma similar
			int c;
			do { c = nextByte(); } while (c <= ' ');
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = nextByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') throw new InputMismatchException();
				res = 10 * res + c - '0';
				c = nextByte();
			} while (c > ' ');
			return res * sgn;
		}
		public double nextDouble() { return Double.parseDouble(next()); }
	}
	// EndCodeSnip
}

from collections import deque
 
n, m = list(map(int, input().split()))
tracks = [input() for _ in range(n)]
 
depth = [[0] * m for _ in range(n)]
q = deque([(0, 0)])
depth[0][0] = 1
 
max_animals = 1
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
 
while q:
	r, c = q.popleft()
	max_animals = max(max_animals, depth[r][c])
 
	for dr, dc in directions:
		nr, nc = r + dr, c + dc
 
		if 0 <= nr < n and 0 <= nc < m and tracks[nr][nc] != ".":
			if depth[nr][nc] == 0:
				if tracks[nr][nc] == tracks[r][c]:
					depth[nr][nc] = depth[r][c]
					q.appendleft((nr, nc))
				else:
					depth[nr][nc] = depth[r][c] + 1
					q.append((nr, nc))
 
print(max_animals)