暴力枚举

起点统计

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1005][1005];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// 返回 x y 能走多长
int dfs(int x, int y)
{
    int res = 1;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (1 <= xx && xx <= n &&
            1 <= yy && yy <= m &&
            a[x][y] != a[xx][yy] &&
            a[x][y] % a[xx][yy] == 0)
            res = max(res, dfs(xx, yy) + 1);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, dfs(i, j));
    cout << ans;
    return 0;
}

终点统计

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[1005][1005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y, int sum)
{
    ans = max(ans, sum);
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 1 && xx <= n &&
            yy >= 1 && yy <= m &&
            a[x][y] % a[xx][yy] == 0 &&
            a[x][y] != a[xx][yy])
            dfs(xx, yy, sum + 1);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dfs(i, j, 1);
    cout << ans;
    return 0;
}

记忆化搜索

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1005][1005];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// 记忆化搜索
// 记住 dfs(i,j) 的值，如果为 0 表示没算过
int book[1005][1005];
// 返回 x y 能走多长
int dfs(int x, int y)
{
    // 如果之前算过了，直接返回结果
    if (book[x][y] != 0)
        return book[x][y];
    int res = 1;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (1 <= xx && xx <= n &&
            1 <= yy && yy <= m &&
            a[x][y] != a[xx][yy] &&
            a[x][y] % a[xx][yy] == 0)
            res = max(res, dfs(xx, yy) + 1);
    }
    // 先记录再返回
    return book[x][y] = res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, dfs(i, j));
    cout << ans;
    return 0;
}