路徑之謎

小明冒充X星球的騎士，進(jìn)入了一個(gè)奇怪的城堡。
城堡里邊什么都沒有，只有方形石頭鋪成的地面。
假設(shè)城堡地面是 n x n 個(gè)方格。【如圖1.png】所示。


按習(xí)俗，騎士要從西北角走到東南角。
可以橫向或縱向移動(dòng)，但不能斜著走，也不能跳躍。
每走到一個(gè)新方格，就要向正北方和正西方各射一箭。
（城堡的西墻和北墻內(nèi)各有 n 個(gè)靶子）
同一個(gè)方格只允許經(jīng)過一次。但不必做完所有的方格。
如果只給出靶子上箭的數(shù)目，你能推斷出騎士的行走路線嗎？
有時(shí)是可以的，比如圖1.png中的例子。
本題的要求就是已知箭靶數(shù)字，求騎士的行走路徑（測(cè)試數(shù)據(jù)保證路徑唯一）

輸入：
第一行一個(gè)整數(shù)N(0<N<20)，表示地面有 N x N 個(gè)方格
第二行N個(gè)整數(shù)，空格分開，表示北邊的箭靶上的數(shù)字（自西向東）

第三行N個(gè)整數(shù)，空格分開，表示西邊的箭靶上的數(shù)字（自北向南）

輸出：
一行若干個(gè)整數(shù)，表示騎士路徑。

為了方便表示，我們約定每個(gè)小格子用一個(gè)數(shù)字代表，從西北角開始編號(hào): 0,1,2,3....
比如，圖1.png中的方塊編號(hào)為：
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

程序應(yīng)該輸出：
0 4 5 1 2 3 7 11 10 9 13 14 15

資源約定：
峰值內(nèi)存消耗 < 256M
CPU消耗? < 1000ms

請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入...” 的多余內(nèi)容。

所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

思路：就是DFS，啥也沒有，題干一如既往的長，唯一復(fù)雜的就是變量多了些。我們直接錯(cuò)（0，0）進(jìn)行搜素，遍歷每個(gè)結(jié)點(diǎn)，同時(shí)保證符合要求即可（注意每次col和row要往同一個(gè)方向進(jìn)行）。看來是有必要認(rèn)真梳理一下類似的題目了。

這樣的搜素必然要有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;//標(biāo)定每個(gè)單元格的數(shù)字static int[] map;//記錄打印順序，長度為（rowSum+colSum）/2，即len的最終值static int len = 0;//記錄路徑的行進(jìn)長度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 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] = 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要往同一個(gè)方向進(jìn)行，即同時(shí)加減。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++;}}} }

總結(jié)

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

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