移動矩陣的問題求解方法

題目介紹

最近練題的過程中，遇到這么一種情況：在一個二維矩陣中，有一個小的固定的圖形，需要移動這個小的圖形到達某個指定的位置，求最短距離。

圖形化的題目看起來長下面這個樣子：

其中：

• ??S：表示起始位置

• ??O：表示目標位置，S?接觸到?O?為終止條件

• ??W：表示水域，是不可通過的區(qū)域

這個圖還沒看明白題目的話，不要緊?？聪旅孢@張圖?。?！

對滴！就是90坦克大戰(zhàn)的簡易版（暴露年齡，哈哈~），只不過我們題目的設(shè)定沒那么復(fù)雜，坦克也不能轉(zhuǎn)向。 下面就來看看代碼吧！

代碼實現(xiàn)

以下代碼僅表述核心算法邏輯，請忽略變量初始化等問題哈~

import?java.util.ArrayDeque;
import?java.util.ArrayList;
import?java.util.List;
import?java.util.Queue;

/**
?*?在一個二維矩陣中移動固定圖案（一個小的矩陣，即多個元素的組合，其兩兩之間的相對位置不變）
?*?求其到位某個滿足條件位置的最小距離解法
?*/
public?class?MoveArray?{
????//?矩陣規(guī)模，R行C列
????static?int?R,?C;
????//?矩陣地圖
????static?char[][]?MAP;

????//?待移動的圖形的點的集合
????static?List<int[]>?BODY;
????//?上下左右移動的偏移量
????static?int[][]?MOVE?=?new?int[][]{{0,?1},?{0,?-1},?{1,?0},?{-1,?0}};

????static?Queue<List<int[]>>?QUEUE;
????static?List<int[]>?NEXT_ITEMS;
????static?boolean[][]?VISITED;

????static?int?ANS;

????/**
?????*?測試入口
?????*/
????public?static?void?main(String[]?args)?{
????????initData();
????????ANS?=?resolve();
????????System.out.println(ANS);
????}

????/**
?????*?初始化數(shù)據(jù)
?????*/
????private?static?void?initData()?{
????????MAP?=?new?char[R][C];
????????VISITED?=?new?boolean[R][C];
????????QUEUE?=?new?ArrayDeque<>();
????????NEXT_ITEMS?=?new?ArrayList<>();
????????ANS?=?0;

????????QUEUE.offer(BODY);
????????for?(int[]?cell?:?BODY)?{
????????????//?將指定的點的集合標記為已訪問
????????????VISITED[cell[0]][cell[1]]?=?true;
????????}
????}

????/**
?????*?求解過程（標準BFS過程）
?????*?@return?最小距離（也可以直接用ANS，不用返回值）
?????*/
????private?static?int?resolve()?{
????????while?(!QUEUE.isEmpty())?{
????????????ANS++;
????????????while?(!QUEUE.isEmpty())?{
????????????????List<int[]>?body?=?QUEUE.poll();
????????????????for?(int[]?shift?:?MOVE)?{
????????????????????boolean[]?result?=?how(body,?shift);
????????????????????if?(!result[0])?{
????????????????????????//?當前偏移不可達，繼續(xù)下一個偏移檢查
????????????????????????continue;
????????????????????}
????????????????????if?(result[1])?{
????????????????????????//?終止條件達成，返回當前距離（最小距離）
????????????????????????return?ANS;
????????????????????}
????????????????????//?當前偏移可通過，加入下一次偏移的集合
????????????????????List<int[]>?moved?=?new?ArrayList<>();
????????????????????for?(int[]?cell?:?body)?{
????????????????????????int?nx?=?cell[0]?+?shift[0];
????????????????????????int?ny?=?cell[1]?+?shift[1];

????????????????????????//?添加新的偏移后的點
????????????????????????moved.add(new?int[]{nx,?ny});
????????????????????????//?設(shè)置新的偏移點未已訪問
????????????????????????VISITED[nx][ny]?=?true;
????????????????????}
????????????????????NEXT_ITEMS.add(moved);
????????????????}
????????????}
????????????QUEUE.addAll(NEXT_ITEMS);
????????????NEXT_ITEMS.clear();
????????}
????????return?-1;
????}

????private?static?boolean[]?how(List<int[]>?body,?int[]?shift)?{
????????//?是否可達標記
????????boolean?couldGo?=?false;
????????//?是否滿足終止條件標記
????????boolean?touch?=?false;

????????for?(int[]?cell?:?body)?{
????????????int?nx?=?cell[0]?+?shift[0];
????????????int?ny?=?cell[1]?+?shift[1];
????????????if?(nx?>=?0?&&?nx?<?R?&&?ny?>=?0?&&?ny?<?C)?{
????????????????//?偏移的點在MAP范圍內(nèi)，進一步判斷
????????????????if?('O'?==?MAP[nx][ny])?{
????????????????????//?滿足終止條件，變更標記
????????????????????touch?=?true;
????????????????}
????????????????if?('W'?==?MAP[nx][ny])?{
????????????????????//?偏移后的點不可達，修改可達標記，跳出
????????????????????//?因為下一個if的判斷，此處必須修改可達標記！
????????????????????couldGo?=?false;
????????????????????break;
????????????????}
????????????????if?(!VISITED[nx][ny])?{
????????????????????//?任意一個偏移后的點未訪問，則認為此次偏移后的整體未訪問過，修改可達標記
????????????????????couldGo?=?true;
????????????????}
????????????}?else?{
????????????????//?偏移的點在MAP范圍外，該偏移不可達，跳出
????????????????couldGo?=?false;
????????????????break;
????????????}
????????}

????????return?new?boolean[]{couldGo,?touch};
????}
}

最后

以上算法就是對此類問題的個人理解，當然這個算法思路在其他類似的模型中也能適用。如果您有更好的解法思路，請留言交流哈~

原文：https://www.jeremysong.cn/cn/move-array/

歡迎關(guān)注我的公眾號“須彌零一”，更多技術(shù)文章第一時間推送。