自动搬运

查看原文

来自洛谷，原作者为

	KukCair 等待秋去春来 / 等待下一次花开 / 在咫尺的未来

搬运于2025-08-24 23:08:34，当前版本为作者最后更新于2025-01-18 12:35:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

搜索。

对于每个位置 $(i, j)$，让 $i \times j$ 向 $num_{i, j}$ 连一条边，所以起点为 $1$，终点为 $n \times m$。

然后 bfs/dfs 即可。

$n$ 和 $m$ 别搞反了，不然喜获 $77$ pts。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;      
int m, n;
bool f[1000005];
vector<int> vc[1000005];
void bfs(){
	queue<int> q;
	q.push(1);
	f[1] = 1;
	while(q.size()){
		int fr = q.front();
		q.pop();
		for(int i = 0; i < vc[fr].size(); i++){
			int v = vc[fr][i];
			if(f[v]) continue;
			f[v] = 1;
			q.push(v);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n;
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			int num;
			cin >> num;
			vc[i * j].push_back(num);
		}
	}
	bfs();
	if(f[n * m]) cout << "yes";
	else cout << "no";
	return 0;
}