J5 / S2: Escape Room

Definimos grid[r][c] como el entero en la $r$-ésima fila de la $c$-ésima columna de la grilla de entrada. Sea done[x]=true si podemos alcanzar alguna celda $(r,c)$ tal que $r\cdot c=x$ y false en caso contrario. Si done[x] es true, entonces también sabemos que done[grid[r][c]] es true para todas las celdas $(r,c)$ tales que $r\cdot c=x$.

Así, esencialmente tenemos un grafo dirigido con vértices $1\ldots 10^6$ donde existe una arista dirigida de x a grid[r][c] siempre que $r\cdot c=x$. Queremos comprobar si existe un camino de $1$ a $N\cdot M$ en este grafo.

Por lo tanto, podemos simplemente empezar un DFS desde el vértice $1$ y marcar todos los vértices que visitamos en el arreglo booleano done. Si ponemos done[N*M]=true, entonces existe un camino, y podemos terminar tras imprimir “yes.” Nótese que en el código de abajo, todo[x] denota la lista de adyacencia de x.

#include <bits/stdc++.h>
 
using namespace std;
 
int M, N;
vector<int> todo[1000005];
bool done[1000005];
 
void dfs(int x) {
	if (done[x]) { return; }
	if (x == N * M) {
		cout << "yes" << endl;
		exit(0);
	}
	done[x] = 1;
	for (int &t : todo[x]) { dfs(t); }
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> M >> N;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			int x;
			cin >> x;
			todo[i * j].push_back(x);
		}
	}
	dfs(1);
	cout << "no" << endl;
}