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

解题思路:

注意事项:

参考代码:

import java.util.Scanner;
public class Main {
	public static int n;
	public static int [] brr2 = new int [121]; 
	public static int [] crr2 = new int [121];
	public static Node [] Path = new Node [121]; 
	public static int [][] arr =new int [121][121];
	public static int [][] vis =new int [121][121];
	public static int [] xx = {-1,1,0,0};
	public static int [] yy = {0,0,1,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i = 0; i < n; i++){
			crr2[i] = sc.nextInt();
		}
		for(int i = 0; i < n; i++){
			brr2[i] = sc.nextInt();
		}
		int num = 0;
		for(int i =0; i < n; i++){
			for(int j = 0; j < n; j++){
				arr[i][j] = num++; 
			}
		}
		vis[0][0] =1;
		DFS(0, 0,0);
		
	}
	public static void DFS(int a, int b, int step){
		if(a == n - 1&&b == n -1){
			int [] brr = new int [121];
			int [] crr = new int [121];
			brr[0]=1;
			crr[0]=1;
			for(int i = 0; i < step; i++){
				brr[Path[i].x]++;
				crr[Path[i].y]++;
			}
			int i;
			for(i = 0; i < n;i++){
				if(crr[i]!=crr2[i]||brr[i]!=brr2[i]){
					break;
				}
			}
			if(i == n){
				System.out.print("0 ");
				for(int k = 0; k < step; k++){
					System.out.print(arr[Path[k].x][Path[k].y]+" ");
				}
			}
		}
		else{
			for(int i = 0; i < 4; i++){
				int zx = a + xx[i];
				int zy = b + yy[i];
				if(zx>=0&&zx<n&&zy>=0&&zy<n&&vis[zx][zy]==0){
					vis[zx][zy] =1;
					Path[step] = new Node(zx,zy);
					DFS(zx, zy, step+1);
					vis[zx][zy]=0;
				}
			}
		}
	}
}
class Node{
	int x;
	int y;
	public Node(int x, int y){
		this.x=x;
		this.y=y;
	}
}