蓝桥杯2016年第七届真题-路径之谜-题解（C语言代码）

#include <stdio.h>
int n,a[2][25],b[2][25],c[25][25],d[25][25],e[25],count=0;//a用来存放目标箭靶数（输入），b存放走过的路径射中的箭靶数（和a进行对比），c用来标记是否走过，d存放是第几个块
//e存放输出的路径 
int dx[4]={0,1,-1,0};	//四个方向 
int dy[4]={1,0,0,-1};
int judge1()	//判断走过的路径的箭靶数是否与目标相同 
{
	int i;
	for(i=0;i<n;i++)
		if(a[0][i]!=b[0][i]||a[1][i]!=b[1][i])
			return 0;
	return 1;
}
void dfs(int x1,int y1,int step)
{	int i,j;
	if(x1==n-1&&y1==n-1)	//到达终点 
		{
		if(judge1()==1)	//与目标靶数相同 
			{
				for(i=0;i<count;i++)	//输出 
					printf("%d ",e[i]);
			}		
		return ;
		}
	else {
		int m;
		for(m=0;m<4;m++)
			{
				int x2=x1+dx[m];
				int y2=y1+dy[m];
				if(c[x2][y2]==0&&x2>=0&&x2<n&&y2>=0&&y2<n)//未被走过，在方格内 
					{
						b[0][y2]++;	//靶数加一 
						b[1][x2]++;
						c[x2][y2]=step;	 //等于1也可以，等于step输出可以看出来走的路径 
						e[count]=d[x2][y2];	//保存路径 
						count++;
						dfs(x2,y2,step+1);	//继续往下搜索，回溯 
						b[0][y2]--;
						b[1][x2]--;
						c[x2][y2]=0;
						e[count]=0;
						count--;
					}
			}
	}
}
int main()
{
	scanf("%d",&n);
	int i,j,cou=0;
	for(i=0;i<n;i++)
		scanf("%d",&a[0][i]);
	for(i=0;i<n;i++)
		scanf("%d",&a[1][i]);
	for(i=0;i<n;i++)	//保存块数 
		for(j=0;j<n;j++)
			{
				d[i][j]=cou;
				cou++;
			}
	e[0]=0;	//初始化 
	count++;
	c[0][0]=1;
	b[0][0]=b[1][0]=1;
	dfs(0,0,2);
	return 0;
 }