网站格局,深圳网站策划推广,做网站绑定域名 解析域名,全国最火的加盟项目路径之谜小明冒充X星球的骑士#xff0c;进入了一个奇怪的城堡。
城堡里边什么都没有#xff0c;只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。按习俗#xff0c;骑士要从西北角走到东南角。
可以横向或纵向移动#xff0c;但不能斜着走进入了一个奇怪的城堡。
城堡里边什么都没有只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。按习俗骑士要从西北角走到东南角。
可以横向或纵向移动但不能斜着走也不能跳跃。
每走到一个新方格就要向正北方和正西方各射一箭。
城堡的西墙和北墙内各有 n 个靶子
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目你能推断出骑士的行走路线吗
有时是可以的比如图1.png中的例子。
本题的要求就是已知箭靶数字求骑士的行走路径测试数据保证路径唯一输入
第一行一个整数N(0N20)表示地面有 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否则按无效代码处理。
思路就是DFS啥也没有题干一如既往的长唯一复杂的就是变量多了些。我们直接错00进行搜素遍历每个结点同时保证符合要求即可注意每次col和row要往同一个方向进行。看来是有必要认真梳理一下类似的题目了。
这样的搜素必然要有vis[][]记录是否遍历必然要有dir[][]控制方向。 告诫自己以后注意采用匈牙利命名法类似iMax。
完整代码如下
import java.util.Scanner;public class Main {static int n;static int[] row, col;static int rowSum;static int colSum;static int[][] print;//标定每个单元格的数字static int[] map;//记录打印顺序长度为rowSumcolSum/2即len的最终值static int len 0;//记录路径的行进长度static int[][] vis;static int[][] dir {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();row new int[n 1];col new int[n 1];vis new int[n 1][n 1];print new int[n 1][n 1];map new int[n*n 1];int index 0;for(int i0; in; i) {for(int j0; jn; j) {print[i][j] index;}}for (int i 0; i n; i) {row[i] in.nextInt();rowSum row[i];}for (int i 0; i n; i) {col[i] in.nextInt();colSum col[i];}len 1;vis[0][0] 1;row[0]--;rowSum--;col[0]--;colSum--;map[0] 0;f(0, 0);}private static void f(int x, int y) {// TODO Auto-generated method stubif (x n - 1 y n - 1) {if (colSum 0 rowSum 0) {for (int i 0; i len; i) {System.out.print(map[i] );}}}for (int i 0; i 4; i) {int dx x dir[i][0];int dy y dir[i][1];if (dx 0 dx n dy 0 dy n vis[dx][dy] 0 row[dy] 0 col[dx] 0) {
// row和col要往同一个方向进行即同时加减。vis[dx][dy] 1;row[dy]--;rowSum--;col[dx]--;colSum--;map[len] print[dx][dy];f(dx, dy);len--;vis[dx][dy] 0;row[dy];rowSum;col[dx];colSum;}}}
}
