路徑之謎小明冒充X星球的騎士，進(jìn)入了一個(gè)奇怪的城堡。城堡里邊什么都沒(méi)有，只有方形石頭鋪成的地面。假設(shè)城堡地面是 n x n 個(gè)方格。【如圖1.png】所示。按習(xí)俗，騎士要從西北角走到東南角。可以橫向或縱向移動(dòng)，但不能斜著走，也不能跳躍。每走到一個(gè)新方格，就要向正北方和正西方各射一箭。（城堡的西墻和北墻內(nèi)各有 n 個(gè)靶子）同一個(gè)方格只允許經(jīng)過(guò)一次。但不必做完所有的方格。如果只給出靶子上箭的數(shù)目，你能推斷出騎士的行走路線嗎？有時(shí)是可以的，比如圖1.png中的例子。本題的要求就是已知箭靶數(shù)字，求騎士的行走路徑（測(cè)試數(shù)據(jù)保證路徑唯一）輸入：第一行一個(gè)整數(shù)N(0<N<20)，表示地面有 N x N 個(gè)方格第二行N個(gè)整數(shù)，空格分開(kāi)，表示北邊的箭靶上的數(shù)字（自西向東）第三行N個(gè)整數(shù)，空格分開(kāi)，表示西邊的箭靶上的數(shù)字（自北向南）輸出：一行若干個(gè)整數(shù)，表示騎士路徑。為了方便表示，我們約定每個(gè)小格子用一個(gè)數(shù)字代表，從西北角開(kāi)始編號(hào): 0,1,2,3....比如，圖1.png中的方塊編號(hào)為：0 1 2 34 5 6 78 9 10 1112 13 14 15示例：用戶輸入：42 4 3 44 3 3 3程序應(yīng)該輸出：0 4 5 1 2 3 7 11 10 9 13 14 15資源約定：峰值內(nèi)存消耗 < 256MCPU消耗 < 1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入...” 的多余內(nèi)容。所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后，拷貝提交該源碼。注意：不要使用package語(yǔ)句。不要使用jdk1.7及以上版本的特性。注意：主類(lèi)的名字必須是：Main，否則按無(wú)效代碼處理。 package com.sihai.qijie;import java.util.Scanner; public class _4{static int[] row ;//保存北邊靶子上的數(shù)目static int[] col; //保存西邊靶子的數(shù)目static int[][] vis ; // 標(biāo)記數(shù)組，標(biāo)記迷宮的方格是否走過(guò)static int N; //上下左右四個(gè)方向static int[][] location = {{0,1},{1,0},{0,-1},{-1,0}};//轉(zhuǎn)換成0--N^2-1的數(shù)組，輸出要求 static int[][] print;static int rowSum = 0;//北邊靶子的總數(shù)目static int colSum = 0;//西邊靶子的總數(shù)目static int[] map = null; //滿足要求的行走路徑static int aLen =1; //可行路徑的長(zhǎng)度public static void main(String[] args){Scanner sc = new Scanner(System.in);N = sc.nextInt();//初始化數(shù)據(jù)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++;//輸入數(shù)據(jù)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];}//開(kāi)始計(jì)算row[0]--;rowSum--;col[0]--;colSum--;vis[0][0] = 1;map[0] = 0;//從0,0出發(fā)dfs(0,0);}public static void dfs(int x, int y){if(x==N-1 && y==N-1){//打印結(jié)果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.沒(méi)出界，2.行列上的靶子數(shù)目至少為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數(shù)組的aLen--vis[dx][dy] = 0;row[dy]++;rowSum++;col[dx]++;colSum++;}}} }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯java第七届决赛第四题--路径之谜的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。