题目描述
给定一个 $M$ 行 $N$ 列的方格矩阵,行从上到下依次编号为 $1 \sim M$,列从左到右依次编号为 $1 \sim N$。
第 $r$ 行第 $j$ 列的方格用 $(r,c)$ 表示。
你需要从方格 $(1,1)$ 出发前往方格 $(M,N)$。
在矩阵中的行进规则如下:
每个方格都有一个权值,当你位于权值为 $x$ 的方格时,你可以跳转到满足 $a \times b = x$ 的任何方格 $(a,b)$。
例如,当你位于权值为 $6$ 的方格时,你可以跳转到方格 $(2,3)$、$(3,2)$、$(1,6)$ 或 $(6,1)$。
注意,跳跃时不能跳到界外或不存在的方格中。
例如,当矩阵一共只有 $5$ 行时,你不可能跳转到方格 $(6,1)$。
请你判断,你是否能够从方格 $(1,1)$ 出发并顺利到达方格 $(M,N)$。
输入格式
第一行包含整数 $M$。
第二行包含整数 $N$。
接下来 $M$ 行,每行包含 $N$ 个整数,其中第 $r$ 行第 $c$ 列的整数表示方格 $(r,c)$ 的权值。
输出格式
如果从方格 $(1,1)$ 出发可以顺利到达方格 $(M,N)$,则输出 yes
,否则输出 no
。
数据范围
$1 \le M,N \le 1000$,
方格权值的取值范围 $[1,10^6]$。
输入样例:
3
4
3 10 8 14
1 11 12 12
6 2 3 9
输出样例:
yes
样例解释
两种可行路线如下:
路线一:$(1,1)$(权值为 $3$)$\to$ $(1,3)$(权值为 $8$)$\to$ $(2,4)$(权值为 $12$)$\to$ $(3,4)$。
路线二:$(1,1)$(权值为 $3$)$\to$ $(3,1)$(权值为 $6$)$\to$ $(2,3)$(权值为 $12$)$\to$ $(3,4)$。
算法思路
- 对于所有合法的位置坐标$(i,j)$,给定一个权值$w$最多可以对应多少合法的位置,此步骤(预处理)方便最初数组大小的开辟,最终结果为$58$
- 正向求解,依次枚举权值$w$,通过寻找其因数来依次增加该权值$w$所能跳到的合法位置 (可参考:AcWing 866 试除法判定质数),时间复杂度:$O(n\ sqrt(n))$,很明显$1e+9$会$TLE$
- 逆向求解,首先开辟数组$cnt[w]$,用于记录权值$w$可以跳转的合法位置的个数,权值$w$的规模为$1e+6$,依次遍历每一个位置即可,时间复杂度:$O(n)$
预处理
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e+6 + 10;
int cnt[N];
int main()
{
int res = 0;
for (int i = 1; i <= 1000; i ++)
{
for (int j = 1; j <= 1000; j ++)
{
cnt[i * j] ++;
res = max(res, cnt[i * j]);
}
}
printf("%d\n", res);
return 0;
}
题解
- 创建结构体$Point$存储点的行列值,$points[W]$存储权值$w$可以跳转到的点
- $st[N][N]$数组确保每一个点只搜索一次
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, W = 1e+6 + 10;
int n, m;
int w[N][N];
struct Point
{
int r, c;
};
vector<Point> points[W];
bool st[N][N];
bool dfs(int r, int c)
{
if (r == n && c == m) return true;
st[r][c] = true;
for (auto p : points[w[r][c]])
{
if (!st[p.r][p.c])
{
if (dfs(p.r, p.c)) return true;
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &w[i][j]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
points[i * j].push_back({i, j});
if (dfs(1, 1)) puts("yes");
else puts("no");
return 0;
}