如果觉得不错 请帮忙点个赞赞 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;
}