1796: 蛇形填数（dfs）

解题思路:

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

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

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

首先让第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;
}