范★老板的~矩阵~！

题目背景

很久很久以前，范♂老板有一个矩★阵。

题目描述

给定一个$n*m$的矩阵，每个位置是一个整数

在四连通意义下，找一条最长的路径，使得路径上数字形成一个等比数列，且公比为整数

输出这个路径长度，如果路径长度为无穷则输出$-1$

注意：这里的路径不一定是简单路径

输入格式

第一行两个数$n,m$,表示矩阵大小

下面$n$行，每行$m$个数(用空格分开),表示这个矩阵

输出格式

一个数字表示答案

样例 #1

样例输入 #1

2 2
1 2
8 4

样例输出 #1

4

样例 #2

样例输入 #2

2 2
1 1
1 1

样例输出 #2

-1

提示

Subtask$1$(10 pts):

所有数字均相同

Subtask$2$(20 pts):

$n*m \leq 100$

Subtask$3$(10 pts):

所有数字均不超过$30$

Subtask$4$(20 pts):

$m=1$

Subtask$5$(40 pts):

无限制

对于所有数据，$n*m \leq 40000$, $1 \leq$矩阵中的数字$\leq 40000$

题意: 题目已经说的很清楚了…还有题目很恶心不给n,m范围只给n*m, 还要动态开数组

思路:

动态数组??? 使用vector

公比怎么解决??? 每次查看下次和这次的比值

每次bfs定义记录数组, 空间, 会炸??? -> 时间也会炸

时间

记录每次的遍历的路径不能以这些为起始点 时间解决

… 好像没解决完

超时的点是无解极限情况, 若是无解极限情况时间复杂度是$O((n * m) ^ 2)$, 一般情况是$O(n * m)$;

需要一个能在 $O(n * m)$ 时间复杂度之内判定无解的代码, 可以发现若两个点的值是相同的就会陷入无限循环即为无解, 至此时间复杂度为$O(n * m)$

空间: 直接在队列中记录即可 空间解决

代码

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

struct Cow
{
    int x, y, dist;
};

int n, m;

int bfs(int x, int y, int k, vector<vector<int>> &w, vector<vector<bool>> &st, vector<vector<int>> &d)
{
    queue<Cow> q;

    q.push({x, y, 1});
    d[x][y] = 1;

    int res = 1;
    while (q.size())
    {
        Cow t = q.front();
        q.pop();

        res = max(res, t.dist);

        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];

            if (a > 0 && a <= n && b > 0 && b <= m && d[a][b] < d[t.x][t.y] + 1 && w[t.x][t.y] * k == w[a][b])
            {
                st[a][b] = true;
                d[a][b] = d[t.x][t.y] + 1;
                q.push({a, b, t.dist + 1});
            }
        }
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    vector<vector<int>> w(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> d(n + 1, vector<int>(m + 1, 0));
    vector<vector<bool>> st(n + 1, vector<bool>(m + 1, 0));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> w[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 4; k++)
            {
                int a = i + dx[k], b = j + dy[k];

                if (a > 0 && a <= n && b > 0 && b <= m && w[i][j] == w[a][b])
                {
                    cout << -1;
                    return 0;
                }
            }

    int res = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!st[i][j])
                for (int k = 0; k < 4; k++)
                {
                    int a = i + dx[k], b = j + dy[k];

                    if (a > 0 && a <= n && b > 0 && b <= m && w[a][b] / w[i][j] * w[i][j] == w[a][b])
                        res = max(res, bfs(i, j, w[a][b] / w[i][j], w, st, d));
                }

    cout << res;


    return 0;
}
/*
1. 动态数组??? : 使用vector
2: 公比怎么解决??? : 每次查看下次和这次的比值
3. 每次bfs定义记录数组, 空间, 会炸??? -> 时间也会炸 
: 记录每次的遍历的路径不能以这些为起始点 时间解决 
... 好像没解决
超时的点是无解极限情况, 若是无解极限情况时间复杂度是O((n*m)^2), 一般情况是O(n*m);
需要一个能在O(n*m)时间复杂度之内判定无解的代码
可以发现若两个点的值是相同的就会陷入无限循环即为无解, 至此时间复杂度为O(n*m)


: 直接在队列中记录即可 空间解决

*/