第七届蓝桥杯决赛JavaB组第四题 路径之谜

之谜"/>

第七届蓝桥杯决赛JavaB组第四题 路径之谜

路径之谜小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入：
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）输出：
一行若干个整数，表示骑士路径。为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....
比如，图1.png中的方块编号为：0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15示例：
用户输入：
4
2 4 3 4
4 3 3 3程序应该输出：
0 4 5 1 2 3 7 11 10 9 13 14 15资源约定：
峰值内存消耗 < 256M
CPU消耗  < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。此题 就是 求从（0,0）至（n-1,n-1）的路线 且要符合 每行每列个数的要求；先说下我的思路， 首先，遍历整个矩阵， 找出 从(0,0)至（n-1,n-1）的 路线， 从路线中判断当前路线的每行每列的个数 符合题目规定的行列个数。

import java.util.Scanner;public class Main5 {private int n;int k = 1; // 用于路径编号 从1开始boolean isFlag[][]; // 用于判断当前数据是否可用int move[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };// 移动坐标点private int row[];// 行的个数private int col[];// 列的个数public static void main(String[] args) {Main5 obj = new Main5();obj.init();}private void init() {Scanner input = new Scanner(System.in);n = input.nextInt();int array[][] = new int[n][n];isFlag = new boolean[n][n];row = new int[n];col = new int[n];for (int i = 0; i < n; i++) {col[i] = input.nextInt();}for (int i = 0; i < n; i++) {row[i] = input.nextInt();}array[0][0] = 1; // 首先把（0,0）标记为走过isFlag[0][0] = true;// isFlag(0,0)为truedfs(array, 0, 0);}private void dfs(int[][] array, int x, int y) { // x 和 y 代表当前点if (x == n - 1 && y == n - 1) { // 这里是 当X 和Y 等于 N-1时，也就代表 到了终点result(array);} else { // 如果没到终点for (int s = 0; s < 4; s++) { // 进行上下左右移动int i = x + move[s][0];int j = y + move[s][1];if (i >= 0 && i < n && j >= 0 && j < n && !isFlag[i][j]) { // 如果// i和j下标在// 0至n-1中// 且// 当前点没有被使用if (judge(array, i, j)) { // 判断 当前的路径 行 和列的个数 必须少于// 规定的行列的个数，如果超出就放弃这个点isFlag[i][j] = true; // 标记当前点被使用array[i][j] = ++k; // 把K放到array 路径中dfs(array, i, j); // dfsisFlag[i][j] = false; // 回溯 取消当前点被使用k--;array[i][j] = 0;}}}}}private boolean judge(int[][] array, int i, int j) {int r[] = new int[n];int c[] = new int[n];r[i]++;c[j]++; // 首先帮当前点 的行列个数 +1for (int w = 0; w < n; w++) {for (int e = 0; e < n; e++) {if (array[w][e] > 0) { // 然后把路径中的行列个数 加1r[w]++;c[e]++;}}}int w = 0;for (w = 0; w < n; w++) {if (r[w] > row[w] || c[w] > col[w]) { // 如果 当前行 列 个数 大于 规定行列的个数// 就breakbreak;}}return w == n ? true : false; // 少于返回true，大于返回false}private void result(int[][] array) { // 若到了终点，则判断此路径 行列的个数 是否符合 规定的行列的个数int r[] = new int[n];int c[] = new int[n];int w = 0;int strData[][] = new int[n][n];for (w = 0; w < n; w++) {for (int e = 0; e < n; e++) {if (array[w][e] > 0) {r[w]++;c[e]++;}}}for (w = 0; w < n; w++) {if (r[w] > row[w] || c[w] > col[w] || r[w] < row[w] || c[w] < col[w]) {break;}}if (w == n) { // 此时 代表着 符合printf(array); //输出路径int s = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {strData[i][j] = s++ ;}}  //按照题目 把 矩阵 画出s = 1; boolean isFlag = true;  while (isFlag) {  //通过 数组中 存放的K的值寻找，  从 1 开始， 一直到 当前点是(n-1,n-1)，此路径就是解for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (array[i][j] == s) {System.out.print(strData[i][j] + " ");if (i == n - 1 && j == n - 1) {isFlag = false;}}}}s++;}}}public void printf(int[][] array) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(array[i][j] + " ");}System.out.println();}System.out.println();}public void printf(boolean[][] array) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(array[i][j] + " ");}System.out.println();}System.out.println();}
}