如果觉得不错 请帮忙点个赞赞 QAQ

搜索方式

相同的步长只需要最小的起点号就行

所以我们就从最小的起点开始找

剪枝

假设一条从$k$可以向走$len$时候

$k\to k+1\to k+2\to \cdots \to k+len-1$

那么再从$k+1$走也只能走到$k+len-1$

所以下一次直接从 $k+len$ 结点向后找就行

存储方式

存每个点在图中的编号是多少

f[k]=(i-1)*n+j-1

这样存储方便找到他属于哪一行哪一列

x=f[k]/n+1 y=f[k]%k+1

存储的规则不唯一 只要能在找到第几行第几列即可

判断是否可以走到相邻的格子

因为只有相邻的格子比自己的数恰好大1才能走到

所以我们可以直接看 下一个能走的数是否就是在我四周

具体代码如下

    int x=f[k]/n+1,y=f[k]%n+1;//取出当前元素的原坐标
    int nx=f[k+1]/n+1,ny=f[k+1]%n+1;//下一个能走到的元素的坐标
    if(x==nx&&(y==ny-1||y==ny+1))return 1+dfs(k+1);//是否在上边或者下边
    if(y==ny&&(x==nx-1||x==nx+1))return 1+dfs(k+1);//是否在左边或者右边

c++代码

#include<iostream>
using namespace std;
const int N=1005;
int t,n;
int f[N*N];
int dfs(int k){//从k开始最多能走多少步
    if(k==n*n)return 1;//走到最后一步了

    int x=f[k]/n+1,y=f[k]%n+1;
    int nx=f[k+1]/n+1,ny=f[k+1]%n+1;
    if(x==nx&&(y==ny-1||y==ny+1))return 1+dfs(k+1);//加上该步走向下一步
    if(y==ny&&(x==nx-1||x==nx+1))return 1+dfs(k+1);

    return 1;//走到k就终止了 就返回1
}
int main(){
    cin>>t;
    for(int u=1;u<=t;u++){
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int x;
                scanf("%d",&x);
                f[x]=(i-1)*n+j-1;//存每一个数字所在的位置编号
            }

        int k=1,res,step=0;//k当前走到哪 res最长的起点编号 step最大能走几步
        while(k<=n*n){
            int len=dfs(k);//从k开始能走几步
            if(len>step){//如果比当前最大步数要大就更新答案
                res=k;
                step=len;
            }
            k+=len;//直接从 k+len开始向后计算
        }
        printf("Case #%d: %d %d\n",u,res,step);
    }
    return 0;
}