网站做政务,网站flash引导页下载,杭州网站建设公司代理加盟,时光轴网站模板路径之谜小明冒充X星球的骑士#xff0c;进入了一个奇怪的城堡。
城堡里边什么都没有#xff0c;只有方形石头铺成的地面。假设城堡地面是 n x n 个方格。【如图1.png】所示。按习俗#xff0c;骑士要从西北角走到东南角。
可以横向或纵向移动#xff0c;但不能斜着走…路径之谜小明冒充X星球的骑士进入了一个奇怪的城堡。
城堡里边什么都没有只有方形石头铺成的地面。假设城堡地面是 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否则按无效代码处理。import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int[] north,west,cur_north,cur_west;static boolean[][] visited;static int n;static int path[];static int cnt0;public static void main(String[] args) {Scanner scan new Scanner(System.in);n scan.nextInt();north new int[n1];westnew int[n1];cur_northnew int[n1];cur_westnew int[n1];pathnew int[n*n1];visitednew boolean[n1][n1];for(int i0;in;i){north[i]scan.nextInt();}for(int i0;in;i){west[i]scan.nextInt();}path[0]0;visited[0][0]true;cur_north[0];cur_west[0];cnt;dfs(0,0);scan.close();}public static boolean check(int i,int j){if(i0||in||j0||jn||visited[i][j]||cur_west[i]west[i]||cur_north[j]north[j]){return false;}return true;}public static void dfs(int i,int j){if(in-1jn-1){for(int a0;an;a){if(cur_north[a]!north[a]||cur_west[a]!west[a]){return;}}path[cnt]i*nj;for(int k1;kcnt;k){System.out.print(path[k] );}System.out.println();return;}if(check(i1, j)){path[cnt]i*nj;visited[i1][j]true;cur_north[j];cur_west[i1];dfs(i1, j);path[--cnt]0;visited[i1][j]false;cur_north[j]--;cur_west[i1]--;}if(check(i-1, j)){path[cnt]i*nj;visited[i-1][j]true;cur_north[j];cur_west[i-1];dfs(i-1, j);path[--cnt]0;visited[i-1][j]false;cur_north[j]--;cur_west[i-1]--;}if(check(i, j1)){path[cnt]i*nj;visited[i][j1]true;cur_north[j1];cur_west[i];dfs(i, j1);path[--cnt]0;visited[i][j1]false;cur_north[j1]--;cur_west[i]--;}if(check(i, j-1)){path[cnt]i*nj;visited[i][j-1]true;cur_north[j-1];cur_west[i];dfs(i, j-1);path[--cnt]0;visited[i][j-1]false;cur_north[j-1]--;cur_west[i]--;}}
}
