網(wǎng)站建設(shè)以推廣外貿(mào)seo推廣
目錄
寫在前面：
題目：P1746 離開(kāi)中山路 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
題目描述：
輸入格式：
輸出格式：
輸入樣例：
輸出樣例：
解題思路：
代碼：
AC ！！！！！！！！！！
寫在最后：
寫在前面：
怎么樣才能學(xué)好一個(gè)算法？
我個(gè)人認(rèn)為，系統(tǒng)性的刷題尤為重要，
所以，為了學(xué)好廣度優(yōu)先搜索，為了用好搜索應(yīng)對(duì)藍(lán)橋杯，
事不宜遲，我們即刻開(kāi)始刷題！
題目：P1746 離開(kāi)中山路 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
題目描述：
輸入格式：
第?1?行包含一個(gè)數(shù)?n。
第?2?行到第 n + 1?行：整個(gè)地圖描述
（00?表示馬路，11?表示店鋪，注意兩個(gè)數(shù)之間沒(méi)有空格）。
第 n + 2?行：四個(gè)數(shù)?x1?, y1?, x2?, y2?。
輸出格式：
只有?11?行，即最短到達(dá)目的地距離。
輸入樣例：
3
001
101
100
1 1 3 3輸出樣例：
4解題思路：
這道題也是一道基礎(chǔ)的迷宮問(wèn)題，
我們用搜索來(lái)做，然后觀察一下他的數(shù)據(jù)范圍，
地圖1000乘1000的大小，
很明顯dfs會(huì)超時(shí)，所以這道題需要使用bfs進(jìn)行搜索，
我們先來(lái)看一下地圖的樣例，模擬一下：
我們從坐標(biāo)1,1開(kāi)始：
?然后直接往四個(gè)方向搜索即可：
?一直搜索到目標(biāo)終點(diǎn)：
?所以最后返回的最短路徑就是4，
那么其實(shí)我們可以發(fā)現(xiàn)，題目中有個(gè)求最短路徑的這個(gè)字眼，
我們可以判斷這道題多半是個(gè)bfs的題目。
根據(jù)這個(gè)思路，我們開(kāi)始實(shí)現(xiàn)代碼：
代碼：
//包好頭文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;const int N = 1010;//存坐標(biāo)
typedef pair<int, int> PII;int n;
int x1, y1, x2, y2;//記錄路徑和
int dist[N][N];//存地圖
char g[N][N];queue<PII> q;//存偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};int bfs(int x1, int y1)
{//將dist初始化為-1memset(dist, -1, sizeof(dist));q.push({x1, y1});//起點(diǎn)dist[x1][y1] = 0;//遍歷到找到終點(diǎn)值或者隊(duì)列為空while(!q.empty()){//取隊(duì)頭auto t = q.front();q.pop();for(int i = 0; i < 4; i++){int a = t.first + dx[i];int b = t.second + dy[i];//控邊界if(a < 1 || a > n || b < 1 || b > n) continue;if(dist[a][b] >= 0) continue;if(g[a][b] != '0') continue;q.push({a, b});//記錄路徑和dist[a][b] = dist[t.first][t.second] + 1;//如果到終點(diǎn)了，就直接返回終點(diǎn)值if(dist[x2][y2] > 0)return dist[x2][y2];}}//如果走不到終點(diǎn)，返回-1return -1;
}int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%s", g[i] + 1);}scanf("%d %d %d %d", &x1, &y1, &x2, &y2);int res = bfs(x1, y1);printf("%d", res);return 0;
}
AC ！！！！！！！！！！
寫在最后：
以上就是本篇文章的內(nèi)容了，感謝你的閱讀。
如果喜歡本文的話，歡迎點(diǎn)贊和評(píng)論，寫下你的見(jiàn)解。
如果想和我一起學(xué)習(xí)編程，不妨點(diǎn)個(gè)關(guān)注，我們一起學(xué)習(xí)，一同成長(zhǎng)。
之后我還會(huì)輸出更多高質(zhì)量?jī)?nèi)容，歡迎收看。