貪吃蛇，迷宮問題
鏈接：https://ac.nowcoder.com/acm/contest/9986/I
來源：牛客網
題目描述
無限增長的貪吃蛇小游戲：
在一個n*m的迷宮中，有一條小蛇，地圖中有很多圍墻，猥瑣的出題者用“#”表示，而可以走的路用“.”表示，小蛇他隨機出生在一個點上，出生點表示為“S”，他想抵達的終點表示為“E”，小蛇有一個奇怪的能力，他每走一格便會增長一格，即他走了一格后，他的尾巴不會碩訓，
小蛇想知道他怎么到達他想去的地方，請你幫助他，
PS：每格長1米，貪吃蛇規定不能撞墻，不能咬自己的身體，
輸入描述:
第一行：輸入N,M；
第二行：輸入S的坐標Xs，Ys，E的坐標Xe，Ye;
后面的N行：
每行輸入M個數，描述每一行的情況，
輸出描述:
輸出一個數，小蛇到達終點的最短距離（單位：cm），若無法達到，輸出-1
示例1
輸入
復制
3 3
1 1 3 3
.#.
.#.
…
輸出
復制
400
示例2
輸入
復制
5 5
1 1 5 5
…###
.#…
.#.#.
.#.#.
…#.
輸出
復制
1400
備注:
對于 100% 的資料：1\le n,m\le 1001≤n,m≤100 ，保證起點不是圍墻，
說一下內心的ruoruo的想法~
我還是太菜了
簽完到之后就來看這個題了
那個簽到的竟然錯了4次，該打，pia
這個題是一個典型的模板題，dfs深搜純純的模板，題的大致意思是說有一條小蛇，從起點到終點，#是障礙物，. 是可以走的，求最短路徑，內心世界很復雜，因為我并不是很熟練
我的思路是把 # 和 . 轉化為 2 和 1，1是通路，2是障礙物，存到一個陣列里a[120][120],再加一個v陣列記錄該點是否經過，0代表未訪問，1代表已訪問
- 看代碼，咱們慢慢仔細講~
- 代碼中dx陣列和dy陣列解釋看這里
#include<bits/stdc++.h>
using namespace std;
int a[120][120];//1 2-->障礙物
int n,m;
int xs,ys,xe,ye;
int minn=99999999;
int v[120][120];//0-->未訪問 1-->訪問
int dx[4]={0,1,0,-1};//對x來說的四個方向!
int dy[4]={1,0,-1,0};//對y來說的四個方向
void dfs(int x,int y,int step){
if(x==xe&&y==ye){//若能到達終點，return
if(step<minn)minn=step;
return ;
}
for(int k=0;k<4;k++){//四個方向
int tx,ty;
tx=x+dx[k];
ty=y+dy[k];
if(a[tx][ty]==1&&v[tx][ty]==0){///是通道&&未訪問
v[tx][ty]=1;//那么就標記為已訪問
dfs(tx,ty,step+1);//已訪問則step+1
v[tx][ty]=0;//回溯完之后再標記為未訪問
}
}
}
int main() {
cin>>n>>m;
cin>>xs>>ys>>xe>>ye;//輸入起點和終點
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>str[i][j];
if(str[i][j]=='.')a[i][j]=1;
else a[i][j]=2;//存進去！
}
}
v[xs][ys]=1;//初始化為1；
dfs(xs,ys,0);//初始step=0
if(minn==99999999)printf("-1");
else
printf("%d",minn*100);
return 0;
}
圖片我調不過來，那我就在最后解釋一下dx dy陣列叭~
假設初始位置是x, y;
int dx[4]={0,1,0,-1};//對x來說的四個方向!
int dy[4]={1,0,-1,0};//對y來說的四個方向
往下走會變成(x+1,y)；對應1，0
往左走會變成（x,y-1);對應0，-1
往上走會變成（x-1,y）;對應-1，0
往右走會變成（x,y+1）；對應0，1；
總而言之，通過這道題我學到了不少知識，希望我們這一批小白都更上一層樓，不要半途而廢，既然選擇了遠方，便只顧風雨兼程，永不停歇！希望以后能看到更加優秀的自己，祝自己，也祝大家，加油！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263756.html
標籤：AI