当前位置: 首页>Python>正文

小青蛙走迷宮的問題

小青蛙走迷宮的問題

小青蛙有一天不小心落入了一個地下迷宮,小青蛙希望用自己僅剩的體力值P跳出這個地下迷宮。為了讓問題簡單,假設這是一個n*m的格子迷宮,迷宮每個位置為0或者1,0代表這個位置有障礙物,小青蛙達到不了這個位置;1代表小青蛙可以達到的位置。小青蛙初始在(0,0)位置,地下迷宮的出口在(0,m-1)(保證這兩個位置都是1,并且保證一定有起點到終點可達的路徑),小青蛙在迷宮中水平移動一個單位距離需要消耗1點體力值,向上爬一個單位距離需要消耗3個單位的體力值,向下移動不消耗體力值,當小青蛙的體力值等于0的時候還沒有到達出口,小青蛙將無法逃離迷宮。現在需要你幫助小青蛙計算出能否用僅剩的體力值跳出迷宮(即達到(0,m-1)位置)。
輸入描述:

輸入包括n+1行:

第一行為三個整數n,m(3 <= m,n <= 10),P(1 <= P <= 100)

接下來的n行:

每行m個0或者1,以空格分隔

輸出描述:

如果能逃離迷宮,則輸出一行體力消耗最小的路徑,輸出格式見樣例所示;如果不能逃離迷宮,則輸出”Can not escape!”。
測試數據保證答案唯一

輸入例子:
4 4 10
1 0 0 1
1 1 0 1
0 1 1 1
0 0 1 1
輸出例子:
[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

分析:該問題屬于迷宮求最短路徑的問題!那么怎么求迷宮最短路徑呢?

迷宮路徑 、最短路徑的問題:
迷宮路徑:使用探測發,用一個棧保存路徑;并且將上一個走過的路徑標記。然后分別取探測改點的上、下、左、右是否可通,如果可通:遞歸進入該點,并把改點入棧;
遞歸的終止條件是到了出口(一般迷宮會規定出口);

最短路徑的問題: 在上個問題的基礎上我們定義個全局的數組 res;用來保存短路徑。之后如果再次找到一條迷宮路徑就和 res比較,如果他的size小于res,就把這條路徑賦值給res

上代碼:

#include<stdio.h>
#include<vector>#include<iostream>
using namespace std;
//將位置封裝成一個結構體,路徑res存放的就是結構體
struct Node
{int x;int y;
};int n,m,p,step = 999999;
vector<Node> res;//保存最優路徑
int a[10][10];//定義了10*10大小的迷宮
bool is_visit[10][10] = { false };//標記走過的位置(true:已經走過;false:還沒走過)void findpath(vector<Node>& tmp, int energy, int i, int j)//運用了遞歸+上下探測的方法;
//如果當前位置的上、下、左、右可通,將其入棧,并且遞歸進去,并將當前位置標記;
//如果這條路不是最優路徑或者不通,遞歸就會返回,再將該位置出棧,并把該位置的標記取消
{if(i == 0 && j == m-1)//走到了出口處{if(energy < p && energy < step)//判斷改路徑是否比上條路徑更好(即比較消耗的能量){step = energy;res = tmp;}return;}//上 if(i-1 >= 0 && a[i-1][j]== 1 && is_visit[i-1][j]==false)//如果這個位置合法,可通并且沒有走過;則進入該位置{energy += 3;Node node;node.x = i-1;node.y = j;tmp.push_back(node);//將該位置入棧is_visit[i-1][j] = true;//標記為走過findpath(tmp, energy, i-1, j);energy -= 3;tmp.pop_back();//出棧is_visit[i-1][j] =false;//取消標記}//右if(j+1 < m && a[i][j+1] == 1 && is_visit[i][j+1] == false){energy += 1;Node node;node.x = i;node.y = j+1;tmp.push_back(node);is_visit[i][j+1] = true;findpath(tmp, energy, i, j+1);energy -= 1;tmp.pop_back();is_visit[i][j+1] =false;}//下if(i+1 < n && a[i+1][j] == 1 && is_visit[i+1][j] == false){energy += 0;Node node;node.x = i+1;node.y = j;tmp.push_back(node);is_visit[i+1][j] = true;findpath(tmp, energy, i+1, j);energy -= 0;tmp.pop_back();is_visit[i+1][j] = false;}//左if(j-1 >= 0 && a[i][j-1] == 1 && is_visit[i][j-1] == false){energy += 1;Node node;node.x = i;node.y = j-1;tmp.push_back(node);is_visit[i][j-1] = true;findpath(tmp, energy, i, j-1);energy -= 1;tmp.pop_back();is_visit[i][j-1] = false;}
}int main()
{cin>>n>>m>>p;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j)cin>>a[i][j];}vector<Node> tmp;int energy = 0;Node node;node.x = 0;node.y = 0;tmp.push_back(node);//將起點保存is_visit[0][0] = true;findpath(tmp, energy, 0, 0);if(step == 999999)cout<<"沒有出路!";else {int i = 0;for(i = 0; i < res.size()-1; ++i){cout<<"["<<res[i].x<<","<<res[i].y<<"]"<<",";}cout<<"["<<res[i].x<<","<<res[i].y<<"]";cout<<endl;}return 0;
}

https://www.nshth.com/python/338731.html
>

相关文章:

  • 國二python難嗎,python字符串(二)
  • 電腦軟件下載app,在電腦上體驗了 16 款手機 App 后,我很失望
  • elasticsearch中文文檔,Elastic安全分析新利器 —— Event Query Language (EQL) 介紹
  • 數據結構與算法python,[FreeCodeCamp筆記] Python 數據結構和算法1 二分搜索 Binary Search
  • 黑蘋果macOS系統鏡像工具,MacOS Monterey 12.2.1 (21D62) OC 0.7.8 / Cl 5144 / PE 三分區原版黑蘋果鏡像
  • 51單片機畢業設計論文,【畢業設計】基于單片機無線充電的4軸飛行器 -物聯網 嵌入式 stm32
  • 數據庫基礎知識整理,數據庫筆記整理
  • python運行不報錯又無任何結果輸出,linux 正確錯誤輸出_報告錯誤的正確方法
  • 計算機組成原理第六版課后答案,杭電計算機組成原理實驗九R-I,杭電計組實驗9-實現R-I型指令的CPU設計實驗.doc
  • python面向對象,Python零基礎速成班-第10講-Python面向對象編程(下),Property屬性、特殊方法、設計模式、鏈表應用
  • 數據庫視圖是什么,【SpringMVC】SpringMVC模型數據+視圖解析器
  • mp3格式轉換器,FFmpeg支持的音頻和視頻編解碼格式
  • 音樂學校招生要求,學校的音樂樓
  • c語言輸入兩個數輸出較大數,C語言求兩個數的較大值
  • 定義一個函數求三個數的最大值,輸入兩個整數,要求輸出其中值較大者。要求用函數求出最大值
  • MySQL學習 DAY1
  • 一個眼神一個微笑就讓人滿足,看得到的微笑
  • centos7安裝MySQL,centos7下載spark連接mysql數據庫提取數據(pyspark,Scala,python獨立執行)
  • node.js開發,從零開始nodejs系列文章-nodejs到底能干什么
  • python控制軟件自動化,Python實現網站自動登錄---傻瓜教程
  • get all of,resent = msg.get_all('Resent-Date') AttributeError: 'str' object h
  • opencv人體動作識別,torchvision使用keypoint rcnn 進行人體關鍵點定位
  • 深度卷積神經網絡原理與實踐,卷積神經網絡resent網絡實踐
  • 服務器,win服務器系統路由器,Windows server 2012 之路由功能
  • 小青蛙走迷宮的問題
  • 漢諾塔-小青蛙
  • 小青蛙oracle跟蹤,在小青蛙TOAD中用oracle語句寫
  • 音頻頻譜分析儀安卓版,[Android]自定義繪制一個簡易的音頻條形圖,附上對MP3音頻波形數據的采集與展現
  • 連乘符號∏的運算法則,∏這個是什么符號?
  • 用例失敗jenkins卻構建成功,jenkins 構建異常_jenkins構建失敗的原因是什么?