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

解题思路:

注意事项:

参考代码:

#include<stdio.h>
int vis[100][100];
int bei[100];
int xi[100];
int xy[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n;
int s[200];
int ri=0;
int flag=0;

int f2();

int f1(int t,int tx,int ty);

void dfs(int tx,int ty);

int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&bei[i]);
	}
	for(j=0;j<n;j++)
	{
		scanf("%d",&xi[j]);
	}
	vis[0][0]=1;
	s[ri]=0;
	ri++;
	dfs(0,0);
	return 0;
}
int f2()
{
	int xx[200]={0};
	int yy[200]={0};
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(vis[i][j])
			yy[i]++;
			if(vis[j][i])
			xx[i]++;
		}
		if(yy[i]!=xi[i]||xx[i]!=bei[i])
		return 0;
	}
	return 1;
}
int f1(int t,int tx,int ty)
{
	tx=tx+xy[t][0];
	ty=ty+xy[t][1];
	if(tx<0||tx>=n||ty<0||ty>=n)
	return 0;
	if(vis[tx][ty])
	return 0;
	return 1;
}
void dfs(int tx,int ty)
{
	int i,j;
	if(tx==n-1&&ty==n-1)
	{
		if(f2())
		{
			for(j=0;j<ri;j++)
			{
				printf("%d ",s[j]);
			}
			printf("\n");
			flag=1;
		}

	}
	for(i=0;i<4;i++)
	{
		if(f1(i,tx,ty))
		{
			tx=tx+xy[i][0];
			ty=ty+xy[i][1];
			vis[tx][ty]=1;
			s[ri]=tx*n+ty;
			ri++;
			dfs(tx,ty);
			if(flag==1)
			return;
			ri--;
			vis[tx][ty]=0;
			tx=tx-xy[i][0];
			ty=ty-xy[i][1];
		}
	}
}