蓝桥杯java第七届决赛第四题--路径之谜

路径之谜小明冒充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 34 5 6 78 9 10 1112 13 14 15示例：用户输入：42 4 3 44 3 3 3程序应该输出：0 4 5 1 2 3 7 11 10 9 13 14 15资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。注意：主类的名字必须是：Main，否则按无效代码处理。 package com.sihai.qijie;import java.util.Scanner; public class _4{static int[] row ;//保存北边靶子上的数目static int[] col; //保存西边靶子的数目static int[][] vis ; // 标记数组，标记迷宫的方格是否走过static int N; //上下左右四个方向static int[][] location = {{0,1},{1,0},{0,-1},{-1,0}};//转换成0--N^2-1的数组，输出要求 static int[][] print;static int rowSum = 0;//北边靶子的总数目static int colSum = 0;//西边靶子的总数目static int[] map = null; //满足要求的行走路径static int aLen =1; //可行路径的长度public static void main(String[] args){Scanner sc = new Scanner(System.in);N = sc.nextInt();//初始化数据row = new int[N];col = new int[N];vis = new int[N][N];print = new int[N][N];map = new int[N*N+1];int index = 0;for(int i=0; i<N; ++i)for(int j=0; j<N; ++j)print[i][j] = index++;//输入数据for(int i=0; i<N; ++i){row[i] = sc.nextInt();rowSum += row[i];}for(int i=0; i<N; ++i){col[i] = sc.nextInt();colSum += col[i];}//开始计算row[0]--;rowSum--;col[0]--;colSum--;vis[0][0] = 1;map[0] = 0;//从0,0出发dfs(0,0);}public static void dfs(int x, int y){if(x==N-1 && y==N-1){//打印结果if(rowSum==0 && colSum==0){for(int i=0; i<aLen; ++i)System.out.print(map[i]+" ");}}for(int i=0; i<4; ++i){int dx = x + location[i][0];int dy = y + location[i][1];//1.没出界，2.行列上的靶子数目至少为1if (dx >= 0 && dx < N && dy >= 0 && dy < N && vis[dx][dy] == 0 && row[dy] > 0 && col[dx] > 0) {vis[dx][dy] = 1;row[dy]--;rowSum--;col[dx]--;colSum--;map[aLen++] = print[dx][dy];dfs(dx, dy);aLen--; //走不通，直接将map数组的aLen--vis[dx][dy] = 0;row[dy]++;rowSum++;col[dx]++;colSum++;}}} }

总结

以上是生活随笔为你收集整理的蓝桥杯java第七届决赛第四题--路径之谜的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。