指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:46332

签 名:

个人博客:blog.imtwa.top

等  级
排  名 11
经  验 25679
参赛次数 49
文章发表 128
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

解题思路:

很久之前就看见这道题了,但是因为感觉模拟起来太复杂所以没有做,今天突然想到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分

161 人评分

  评论区