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

解题思路:
DFS深搜就行，到一个点就把对应的箭靶-1即可，剪枝就过了，附上AC代码
参考代码:

import java.util.*;

public class Main {

	static int N;
	static int[][] mig;
	static int[] col;
	static int[] row;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static Vector road;

	static boolean check() {
		for (int i = 0; i < N; i++)
			if (row[i] != 0 || col[i] != 0)
				return false;
		return true;
	}

	static void dfs(int x, int y) {
		mig[x][y]=1;
		row[x]--;
		col[y]--;
		road.add(x+y*N);
		if (row[x] < 0 || col[y] < 0) {
			mig[x][y]=0;
			row[x]++;
			col[y]++;
			road.remove(road.size()-1);
			return;
		}
		if (x == N - 1 && y == N - 1 && check()) {
			for (int i = 0; i < road.size()-1; i++)
				System.out.print(road.get(i) + " ");
			System.out.print(road.get(road.size()-1));
			System.exit(0);
		}
		for (int i = 0; i < 4; i++)
			if (x + dx[i] >= 0 && x + dx[i] < N && y + dy[i] >= 0 && y + dy[i] < N && mig[x + dx[i]][y + dy[i]] == 0)
				dfs(x + dx[i], y + dy[i]);
		mig[x][y]=0;
		row[x]++;
		col[y]++;
		road.remove(road.size()-1);
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		mig = new int[N + 1][N + 1];
		row = new int[N + 1];
		col = new int[N + 1];
		road = new Vector<>();
		for (int i = 0; i < N; i++)
			row[i] = in.nextInt();
		for (int i = 0; i < N; i++)
			col[i] = in.nextInt();
		dfs(0, 0);

	}
}