解题思路:

很久之前就看见这道题了,但是因为感觉模拟起来太复杂所以没有做,今天突然想到dfs寻路可能可以解这道题,就尝试了一下dfs做法。

image.png

如上图所示,如果从右上角开始的话,优先级一定是先向下搜索,然后再向左搜索,向上,最后向右搜索。

也就是说,我们让搜索的优先级 下>左>上>右就可以了。

首先让第1号位置的向下搜索,如果到到达右下角以后,向下无法搜索了,就开始向左搜索,到达左下角以后,如7号位置,此时向下 向左都无法前进,就向上搜索填数。

转完一圈填满数组,这时候就是我们想要的答案了。

因为和做排列数、搜索迷宫不同,不需要回溯后向下一个方向搜索(回溯搜索也没有用,数组已经填满了),所以在找到一个方向递归以后,下一步就可以break掉了。

但是在模拟的时候发现结果和答案有些出处,检查后发现是11号位置的地方,这个时候它有两种选择(向下和向右),因为规定向下的优先级大于向右,所以在11号位置处会向下搜索填数。但是只有这一个位置有特例,所以对这个位置进行了特判,详见代码注释。


参考代码:

#include <bits/stdc++.h>

using namespace std;

const int S=101;//数组大小

int dx[4]={1,0,-1,0};//下 左 上 右
int dy[4]={0,-1,0,1};//四个方向搜索,优先级下>左>上>右
int p[S][S];//数组存储答案
int n;

void dfs(int x1,int y1,int l){//x1 y1是上一步的坐标,l是当前的数字
	if(!(x1>0&&y1>0&&x1<=n&&y1<=n))return ;//搜索超过数组,return
	 
	if(!p[x1+1][y1]&&!p[x1][y1+1]&&x1+1<=n&&y1+1<=n){//如果有两种方向(下 右)可以走且不超过数组
		p[x1][y1+1]=l; 
		dfs(x1,y1+1,l+1);//就强制向右走
	}
	//cout<<x1<<" "<<y1<<" "<<l-1<<endl;  //可以查看填数的路径
	
	for(int i=0;i<4;i++){//四种方向搜索
		int x=x1+dx[i];
		int y=y1+dy[i];
		if(x>0&&y>0&&x<=n&&y<=n){//不超过数组边界
			if(!p[x][y]){//没有填过数字
				p[x][y]=l;//填数
				dfs(x,y,l+1);//向下一方向走
				break;//找到一个方向就可以了
			}
		}	
	}

}

int main()
{
	while(cin>>n){//多组数据
		memset(p,0,sizeof(p));//每次将数组置0
		p[1][n]=1;
		dfs(1,n,2);//从右上角开始,下一位置为2
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)cout<<p[i][j]<<" \n"[j==n];//打印输出
		}
		cout<<endl;//每组数据间空一行
	}

 	return 0;
}


点赞(0)
 

0.0分

4 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论