一、Flood Fill（連通塊問題）
0.簡介
Flood Fill（洪水覆寫）
可以在線性的時間復雜內，找到某個點所在的連通塊！
注：基于寬搜的思想，深搜也可以做但可能會爆堆疊
flood fill演算法DFS與BFS：
? DFS：無法求解最短路問題；可能會爆堆疊（遞回層數很深時）；代碼簡介，當資料范圍較小時可以使用
? BFS：可以求解最短路；不存在爆堆疊情況；需要自己手寫佇列
1.池塘計數
農夫約翰有一片 N?MN?M 的矩形土地，
最近，由于降雨的原因，部分土地被水淹沒了，
現在用一個字符矩陣來表示他的土地，
每個單元格內，如果包含雨水，則用”W”表示，如果不含雨水，則用”.”表示，
現在，約翰想知道他的土地中形成了多少片池塘，
每組相連的積水單元格集合可以看作是一片池塘，
每個單元格視為與其上、下、左、右、左上、右上、左下、右下八個鄰近單元格相連，
請你輸出共有多少片池塘，即矩陣中共有多少片相連的”W”塊，
**
輸入格式**第一行包含兩個整數 NN 和 MM，
接下來 NN 行，每行包含 MM 個字符，字符為”W”或”.”，用以表示矩形土地的積水狀況，字符之間沒有空格，
輸出格式
輸出一個整數，表示池塘數目，
資料范圍
1≤N,M≤10001≤N,M≤1000
輸入樣例：
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.輸出樣例：
3
思路：
從前往后遍歷，找到一塊水（沒被標記過的），進行Flood Fill得出所在的連通塊，水洼加1，即每一次bfs結束就得到一個連通塊（水洼）
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;// 用來存盤坐標
queue<PII> q;
const int N = 1010 + 10;
char g[N][N];
bool st[N][N];
int n, m, ans;
//八方向
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
// 找出(x,y)所構成的連通塊！
void bfs(int x, int y)
{
q.push({x, y}), st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
//擴展隊頭（遍歷所有鄰接點）
for(int i = 0; i < 8; i ++)
{
int tx = t.first + dx[i];
int ty = t.second + dy[i];
//細節判斷
if(tx < 0 || tx >= n || ty < 0 || ty >= m ) continue;// 越界
if(g[tx][ty] == '.' || st[tx][ty]) continue;// 如果是. 或者雖然是水但被標記過了
//鄰接節點入隊
q.push({tx, ty});
st[tx][ty] = true;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
//讀入地圖
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
//找到水 且 沒有被標記過的 進行foll fill找連通塊
if(g[i][j] == 'W' && !st[i][j])
{
bfs(i, j);
ans ++;
}
}
}
printf("%d", ans);
return 0;
}
【DFS代碼】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, ans;
const int N = 1100;
char g[N][N];
int fx[8]={-1,-1,-1,0,0,1,1,1};
int fy[8]={-1,0,1,-1,1,-1,0,1};
// 如果遇到池塘就計數，并把與他相連通的池塘抽干(用深搜將它們標記為.)
void dfs(int x, int y)
{
// 將被訪問過的水洼標記，避免重復使用
g[x][y] = '.';
// 深搜抽干連通的部分
for(int i = 0; i < 8; i++)
{
int tx = x + fx[i];
int ty = y + fy[i];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && g[tx][ty] == 'W')
{
dfs(tx, ty);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j++)
cin >> g[i][j];
// 依次遍歷每個點，如果是水洼，計數加1，用深搜將連通的水洼抽干
for(int i = 1; i <= n; i++){
for (int j = 1; j <= m; j ++ ){
if(g[i][j] == 'W'){ // 碰到水洼 結果加1，深搜抽干連通的水洼
dfs(i,j);
ans ++;
}
}
}
cout << ans;
return 0;
}
2.紅與黑
有一間長方形的房子，地上鋪了紅色、黑色兩種顏色的正方形瓷磚，
你站在其中一塊黑色的瓷磚上，只能向相鄰（上下左右四個方向）的黑色瓷磚移動，
請寫一個程式，計算你總共能夠到達多少塊黑色的瓷磚，
輸入格式
輸入包括多個資料集合，
每個資料集合的第一行是兩個整數 W 和 H，分別表示 x 方向和 y 方向瓷磚的數量，
在接下來的 HH 行中，每行包括 W 個字符，每個字符表示一塊瓷磚的顏色，規則如下
1）‘.’：黑色的瓷磚；
2）‘#’：紅色的瓷磚；
3）‘@’：黑色的瓷磚，并且你站在這塊瓷磚上，該字符在每個資料集合中唯一出現一次，當在一行中讀入的是兩個零時，表示輸入結束，
輸出格式
對每個資料集合，分別輸出一行，顯示你從初始位置出發能到達的瓷磚數(記數時包括初始位置的瓷磚)，
資料范圍
1≤W,H≤20
輸入樣例：
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0輸出樣例：
45
思路：
遍歷圖，找到起點（但起點），從起點開始flood fill 并統計黑色瓷磚的數量！
【DFS代碼實作】
#include <iostream>
#include <cstring>
#include<cstdio>
#include <algorithm>
using namespace std;
const int N = 30;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, res;
void dfs(int x, int y)
{
g[x][y] = '#';//標記，防止重復訪問
res ++;
for(int i = 0; i < 4; i++ )
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] == '#') continue;
if(g[a][b] == '.')//找到黑色瓷磚，繼續深搜
{
dfs(a, b);
}
}
}
int main()
{
//多組資料輸入
while(cin >> m >> n, n || m)
{
res = 0;//多輸入 每次res要置零 不然結果就累加了！
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
int x, y;
bool flag = false;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
if(g[i][j] == '@')
{
x = i;
y = j;
flag = true;
}
if(flag) break;//找到起點（一個起點） 就可以直接跳出回圈了
}
dfs(x, y);// flood fill
cout << res << endl;
}
return 0;
}
【BFS代碼實作】
#include <iostream>
#include <cstring>
#include<cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 30;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int bfs(int x, int y)
{
int res = 1;
q.push({x, y});
st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(st[a][b]) continue;
if(g[a][b] != '.') continue;
q.push({a, b});
st[a][b] = true;
res ++;
}
}
return res;
}
int main()
{
//多組資料輸入
while(cin >> m >> n, n || m)
{
memset(st,0,sizeof st);// 多組輸入，每次都要恢復！ 為下一次做好準備！
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
int x, y;
bool flag = false;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
if(g[i][j] == '@')
{
x = i;
y = j;
flag = true;
}
if(flag) break;//找到起點（一個起點） 就可以直接跳出回圈了
}
cout << bfs(x, y) << endl;// flood fill
}
return 0;
}
3.城堡問題
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # # | | | | # # ############################# (圖 1) # = Wall | = No wall - = No wall 方向：上北下南左西右東，圖1是一個城堡的地形圖，
請你撰寫一個程式，計算城堡一共有多少房間，最大的房間有多大，
城堡被分割成 m?n個方格區域，每個方格區域可以有0~4面墻，
注意：墻體厚度忽略不計，
輸入格式
第一行包含兩個整數 mm 和 n，分別表示城堡南北方向的長度和東西方向的長度，
接下來 mm 行，每行包含 n 個整數，每個整數都表示平面圖對應位置的方塊的墻的特征，
每個方塊中墻的特征由數字 P 來描述，我們用1表示西墻，2表示北墻，4表示東墻，8表示南墻，P 為該方塊包含墻的數字之和，
例如，如果一個方塊的 P 為3，則 3 = 1 + 2，該方塊包含西墻和北墻，
城堡的內墻被計算兩次，方塊(1,1)的南墻同時也是方塊(2,1)的北墻，
輸入的資料保證城堡至少有兩個房間，
輸出格式
共兩行，第一行輸出房間總數，第二行輸出最大房間的面積（方塊數），
資料范圍
1≤m,n≤50,
0≤P≤15輸入樣例：
4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13輸出樣例：
5 9
思路：
相鄰的點沒有墻則表示連通，一個房間則相當于是一個連通塊，即，找所有的連通塊！—— Flood Fill
從前往后遍歷，把每一個連通塊找出來，找的時候統計兩個數，一個是面積另一個是連通塊的數量
本題難點在于輸入：（并非裸生生的給你坐標）
二進制只相差一位，因此可以使用移位法！
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 50 + 10;
int g[N][N];
bool st[N][N];
int m, n;
int bfs(int x, int y)
{
//西北東南
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int area = 0;
q.push({x, y}), st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
area ++;//面積加1
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
if(st[a][b]) continue;//標記過了
if(g[t.first][t.second] >> i & 1) continue;//有墻
q.push({a, b});
st[a][b] = true;
}
}
return area;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++ )
cin >> g[i][j];
int area = 0, cnt = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if(!st[i][j])
{
area = max(area, bfs(i, j));
cnt ++;
}
cout << cnt << endl;
cout << area << endl;
return 0;
}
4.全球變暖
你有一張某海域 N×N 像素的照片，”.”表示海洋、”#”表示陸地，如下所示：
....... .##.... .##.... ....##. ..####. ...###. .......其中”上下左右”四個方向上連在一起的一片陸地組成一座島嶼，例如上圖就有 22 座島嶼，
由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒，
具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒，
例如上圖中的海域未來會變成如下樣子：
....... ....... ....... ....... ....#.. ....... .......請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒，
輸入格式
第一行包含一個整數N，
以下 N 行 N 列，包含一個由字符”#”和”.”構成的N×N 字符矩陣，代表一張海域照片，”#”表示陸地，”.”表示海洋，
照片保證第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋，
輸出格式
一個整數表示答案，
資料范圍
1≤N≤1000
輸入樣例1：
7 ....... .##.... .##.... ....##. ..####. ...###. .......輸出樣例1：
1輸入樣例2：
9 ......... .##.##... .#####... .##.##... ......... .##.#.... .#.###... .#..#.... .........輸出樣例2：
1
思路：
遍歷所有未遍歷過的陸地，通過bfs計算出當前位置連通陸地的數量total，以及被淹沒陸地的數量bound,若total == bound表示完整淹沒的一個島嶼
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 1010;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n;
//total：當前連通塊#的數量 bound：被淹沒的#的數量
void bfs(int x, int y, int& total, int& bound)
{
q.push({x, y});
st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
total ++;//'#'加1
bool is_bound = false;//判斷島嶼是否被淹沒
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= n) continue;
if(st[a][b]) continue;
if(g[a][b] == '.')//與#相鄰的點是海. 說明該陸地#可以被淹沒
{
is_bound = true;
continue;
}
//未被訪問過的#
q.push({a, b});
st[a][b] = true;
}
if(is_bound) bound ++;//可以被淹沒，被淹沒#的數量 bound ++
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
int cnt = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if(!st[i][j] && g[i][j] == '#')
{
int total = 0, bound = 0;
bfs(i, j, total, bound);
if(total == bound) cnt ++;//如果連通塊中所有的陸地# 都與海. 相鄰，說明會被完全淹沒
}
printf("%d", cnt);
return 0;
}
5.山峰和山谷
FGD小朋友特別喜歡爬山，在爬山的時候他就在研究山峰和山谷，
為了能夠對旅程有一個安排，他想知道山峰和山谷的數量，
給定一個地圖，為FGD想要旅行的區域，地圖被分為 n×nn×n 的網格，每個格子 (i,j)(i,j) 的高度 w(i,j)w(i,j) 是給定的，
若兩個格子有公共頂點，那么它們就是相鄰的格子，如與 (i,j)(i,j) 相鄰的格子有(i?1,j?1),(i?1,j),(i?1,j+1),(i,j?1),(i,j+1),(i+1,j?1),(i+1,j),(i+1,j+1)(i?1,j?1),(i?1,j),(i?1,j+1),(i,j?1),(i,j+1),(i+1,j?1),(i+1,j),(i+1,j+1)，
我們定義一個格子的集合 SS 為山峰（山谷）當且僅當：
- SS 的所有格子都有相同的高度，
- SS 的所有格子都連通，
- 對于 ss 屬于 SS，與 ss 相鄰的 s′s′ 不屬于 SS，都有 ws>ws′ws>ws′（山峰），或者 ws<ws′ws<ws′（山谷），
- 如果周圍不存在相鄰區域，則同時將其視為山峰和山谷，
你的任務是，對于給定的地圖，求出山峰和山谷的數量，如果所有格子都有相同的高度，那么整個地圖即是山峰，又是山谷，
輸入格式
第一行包含一個正整數 nn，表示地圖的大小，
接下來一個 n×nn×n 的矩陣，表示地圖上每個格子的高度 ww，
輸出格式
共一行，包含兩個整數，表示山峰和山谷的數量，
資料范圍
1≤n≤10001≤n≤1000,
0≤w≤1090≤w≤109輸入樣例1：
5 8 8 8 7 7 7 7 8 8 7 7 7 7 7 7 7 8 8 7 8 7 8 8 8 8輸出樣例1：
2 1輸入樣例2：
5 5 7 8 3 1 5 5 7 6 6 6 6 6 2 8 5 7 2 5 8 7 1 0 1 7輸出樣例2：
3 3樣例解釋
樣例1：
樣例2：
根據題目描述
1、沒有比它高的叫山峰
2、沒有比它矮的叫山谷
3、還存在又比它高，又比它矮的不算山峰也不算山谷
步驟
-
找到高度一致的連通塊，若該連通塊周圍
-
沒有存在比它高的則該連通塊叫山峰
-
沒有存在比它矮的則該連通塊叫山谷
-
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 1010;
int h[N][N];
bool st[N][N];
//八方向
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n;
void bfs(int x, int y, bool& has_higher, bool& has_lower)//通過參考傳回
{
q.push({x, y});
st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 8; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= n) continue;
if(h[a][b] != h[t.first][t.second])//山脈邊界:判斷是否在同一個山脈里面
{
if(h[a][b] > h[t.first][t.second]) has_higher = true;//存在比它高的
else has_lower = true;//存在比它低的
}
//高度相等且未遍歷 說明要在同一個連通塊當中 鄰接節點加入佇列 后續繼續擴展它
else if(!st[a][b])
{
q.push({a, b});
st[a][b] = true;
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &h[i][j]);
int peak = 0, valley = 0;
//從前往后遍歷每個格子
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if(!st[i][j])
{
bool has_higher = false, has_lower = false;//用來維護每一個連通塊
bfs(i, j, has_higher, has_lower);//得到一個連通塊 根據兩個布林值的情況判斷！
if(!has_higher) peak ++;//只要沒有比它高的————山峰
if(!has_lower) valley ++;//只要沒有比它矮的————山谷
//注：不能加else 存在既不是山峰也不是山谷的情況
}
printf("%d %d", peak, valley);
return 0;
}
6.奶牛選美
聽說最近兩斑點的奶牛最受歡迎，約翰立即購進了一批兩斑點牛，
不幸的是，時尚潮流往往變化很快，當前最受歡迎的牛變成了一斑點牛，
約翰希望通過給每頭奶牛涂色，使得它們身上的兩個斑點能夠合為一個斑點，讓它們能夠更加時尚，
牛皮可用一個 N×M 的字符矩陣來表示，如下所示：
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....其中，X 表示斑點部分，
如果兩個 X 在垂直或水平方向上相鄰（對角相鄰不算在內），則它們屬于同一個斑點，由此看出上圖中恰好有兩個斑點，
約翰牛群里所有的牛都有兩個斑點，
約翰希望通過使用油漆給奶牛盡可能少的區域內涂色，將兩個斑點合為一個，
在上面的例子中，他只需要給三個 .. 區域內涂色即可（新涂色區域用 ? 表示）：
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ........XXXXX... .........XXX....請幫助約翰確定，為了使兩個斑點合為一個，他需要涂色區域的最少數量，
輸入格式
第一行包含兩個整數 N 和 M，
接下來 N 行，每行包含一個長度為 M 的由 X 和 .. 構成的字串，用來表示描述牛皮圖案的字符矩陣，
輸出格式
輸出需要涂色區域的最少數量，
資料范圍
1≤N,M≤50
輸入樣例：
6 16 ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....輸出樣例：
3
補充：曼哈頓距離
二維坐標下（坐標系）的計算公式：
歐氏距離里的距離計算：
曼哈頓距離中的距離計算：
曼哈頓距離也叫出租車距離（出租車很難以歐氏距離的方式到達另一地點（可能存在障礙物）），用來標明兩個點在標準坐標系上的絕對軸距總和，
圖中紅線代表曼哈頓距離，綠色代表歐氏距離，也就是直線距離，而藍色和黃色代表等價的曼哈頓距離，曼哈頓距離——兩點在南北方向上的距離加上在東西方向上的距離，即d(i,j)=|xi-xj|+|yi-yj|，對于一個具有正南正北、正東正西方向規則布局的城鎮街道，從一點到達另一點的距離正是在南北方向上旅行的距離加上在東西方向上旅行的距離，因此，曼哈頓距離又稱為出租車距離，曼哈頓距離不是距離不變數，當坐標軸變動時，點間的距離就會不同，
【曼哈頓網格的應用場景和意義】
曼哈頓距離示意圖在早期的計算機圖形學中，螢屏是由像素構成，是整數，點的坐標也一般是整數，原因是浮點運算很昂貴，很慢而且有誤差，如果直接使用AB的歐氏距離(歐幾里德距離：在二維和三維空間中的歐氏距離的就是兩點之間的距離），則必須要進行浮點運算，如果使用AC和CB，則只要計算加減法即可，這就大大提高了運算速度，而且不管累計運算多少次，都不會有誤差，
【代碼實作】
思路：
- 從到到尾遍歷，找到
'X'，然后flood fill找出兩個連通塊 - 將兩個連通塊的所有點（坐標）分別存盤到兩個集合當中
- 列舉兩個集合的所有點對，通過曼哈頓距離公式求解最優解
時間復雜度：O(n*n)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII>points[2];// 用vector將兩個連通塊得坐標存盤下來
const int N = 60;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
void dfs(int x, int y, vector<PII>& pos)
{
g[x][y] = '.';//標記
pos.push_back({x, y});//各個X的坐標記錄到集合中
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
{
dfs(a, b, pos);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> g[i];
for (int i = 0, k = 0; i < n; i ++ )
for(int j = 0; j < m; j ++)
if(g[i][j] == 'X')
{
//dfs flood fill得出連通塊，并將連通塊的點存盤到集合中
dfs(i, j, points[k ++]);
}
//這樣就得到了兩個連通塊的點，接下就列舉兩個集合中的所有點 通過曼哈頓距離求最優解
int res = 1e8;
for(auto &a : points[0])
for(auto &b : points[1])
res = min(res, abs(a.first - b.first) + abs(a.second - b.second) - 1);
//直接曼哈頓距離求的是兩點間能互相走到需要的步數， 這題相當于問程序中需要經過的點數， 所以要減一
cout << res;
return 0;
}
注：
? 對于任意兩個點求最短距離，
曼哈頓距離不一定成立，但對于其中距離最近的兩個點（最優解）曼哈頓距離一定是正確的！反證法：假設兩個點之間的距離是最優解，如果求解出來的距離不是最短路，那么就說明兩個初始起終點之間存在障礙物，那么起點或者終點就可以調換到障礙物的位置上，距離就會變短，那么就與條件假設矛盾了！
二、最短路模型
0.簡介
當所有的邊權都相等時，BFS搜索可以得到起點到某個點的最短路（單源最短路徑問題）！
1.走迷宮
我們對st標記陣列進行擴展，在起到標記作用的同時，還起到記錄各點到起點的最短距離作用！——d[N][N]
給定一個 n×m 的二維整數陣列，用來表示一個迷宮，陣列中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通過的墻壁，
最初，有一個人位于左上角 (1,1) 處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置，
請問，該人從左上角移動至右下角 (n,m) 處，至少需要移動多少次，
資料保證 (1,1) 處和 (n,m) 處的數字為 0，且一定至少存在一條通路，
輸入格式
第一行包含兩個整數 n 和 m，
接下來 n 行，每行包含 mm 個整數（0或 1），表示完整的二維陣列迷宮，
輸出格式
輸出一個整數，表示從左上角移動至右下角的最少移動次數，
資料范圍
1≤n,m≤100
輸入樣例：
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0輸出樣例：
8
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 110;
int g[N][N];
int d[N][N]; //存放各個點到起點的距離
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int bfs()
{
memset(d, -1, sizeof d);//初始距離全部設定為-1 表示該點未被訪問過（記錄距離的同時，起到了st陣列的作用）
q.push({0, 0});
d[0][0] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
if(g[a][b]) continue;//撞墻
if(d[a][b] != -1) continue;//該點被訪問過
q.push({a, b});
d[a][b] = d[t.first][t.second] + 1;//更新距離
}
}
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++)
cin >> g[i][j];
cout << bfs();
return 0;
}
2.迷宮問題
上述第1題走迷宮的擴展版，BFS如何記錄路徑問題（最短路）！
BFS常常用到標記陣列st，同樣的我們對st陣列進行擴展，在起到標記作用的同時，起到記錄路徑的作用！
pair<int , int> pre[N][N]——存放當前位置的前驅（看看這個點是從哪里來的），當我們走到終點時，就可以反推到前一步在哪，進而得出最短路的路徑！
給定一個 n×n 的二維陣列，如下所示：
int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程式找出從左上角到右下角的最短路線，
資料保證至少存在一條從左上角走到右下角的路徑，
輸入格式
第一行包含整數 n，
接下來 n 行，每行包含 n 個整數 0 或 1，表示迷宮，
輸出格式
輸出從左上角到右下角的最短路線，如果答案不唯一，輸出任意一條路徑均可，
按順序，每行輸出一個路徑中經過的單元格的坐標，左上角坐標為 (0,0)，右下角坐標為 (n?1,n?1)，
資料范圍
0≤n≤1000
輸入樣例：
5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0輸出樣例：
0 0 1 0 2 0 2 1 2 2 2 3 2 4 3 4 4 4
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 1010;
int g[N][N];
PII pre[N][N];// 記錄當前位置的前驅
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n;
void bfs(int x, int y)
{
q.push({x, y});
pre[0][0] = {0, 0};//起點的前驅（不用標記也行，我們存的是點的前驅！）
memset(pre, -1, sizeof pre);//pre陣列存放這個點的上一個點，初始化為-1
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= n) continue;
if(g[a][b]) continue;
if(pre[a][b].first != -1) continue;//當前點被訪問過
q.push({a, b});
pre[a][b] = t;
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &g[i][j]);
bfs(n - 1, n - 1);//逆序搜索,正序列印
PII end(0, 0);//定義起點
while(true)
{
printf("%d %d\n", end.first, end.second);// 從前點開始輸出路徑
if(end.first == n - 1 && end.second == n - 1) break;// 到了終點
end = pre[end.first][end.second];// 沒到終點拿到前驅位置
}
return 0;
}
3.武士風度的牛
這題也是第1題走迷宮的擴展，求某一個起點到某一個終點的最短距離，不同的是這頭牛是以馬走日的形式遍歷！
農民 John 有很多牛，他想交易其中一頭被 Don 稱為 The Knight 的牛，
這頭牛有一個獨一無二的超能力，在農場里像 Knight 一樣地跳（就是我們熟悉的象棋中馬的走法），
雖然這頭神奇的牛不能跳到樹上和石頭上，但是它可以在牧場上隨意跳，我們把牧場用一個x，y 的坐標圖來表示，
這頭神奇的牛像其它牛一樣喜歡吃草，給你一張地圖，上面標注了 The Knight 的開始位置，樹、灌木、石頭以及其它障礙的位置，除此之外還有一捆草，
現在你的任務是，確定 The Knight 要想吃到草，至少需要跳多少次，
The Knight 的位置用
K來標記，障礙的位置用*來標記，草的位置用H來標記，這里有一個地圖的例子：
11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . H 5 | * . . . . . . . . . 4 | . . . * . . . * . . 3 | . K . . . . . . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0The Knight 可以按照下圖中的A,B,C,D… 這條路徑用 55 次跳到草的地方（有可能其它路線的長度也是 5）：
11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . F< 5 | * . B . . . . . . . 4 | . . . * C . . * E . 3 | .>A . . . . D . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0注意： 資料保證一定有解，
輸入格式
第 1 行： 兩個數，表示農場的列數 C 和行數 R，
第 2..R+1 行: 每行一個由 C 個字符組成的字串，共同描繪出牧場地圖，
輸出格式
一個整數，表示跳躍的最小次數，
資料范圍
1≤R,C≤150
輸入樣例：
10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*..輸出樣例：
5
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 160;
char g[N][N];
int d[N][N];
//日字形八方向
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;
int bfs()
{
int x, y;// 起點位置
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if(g[i][j] == 'K')
x = i, y = j;
q.push({x, y});
memset(d, -1, sizeof d);
d[x][y] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 8; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(g[a][b] == '*') continue;
if(d[a][b] != -1) continue;
if(g[a][b] == 'H') return d[t.first][t.second] + 1;
q.push({a, b});
d[a][b] = d[t.first][t.second] + 1;
}
}
return -1;//沒有答案
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> g[i];
cout << bfs();
return 0;
}
4.抓住那頭牛
農夫知道一頭牛的位置，想要抓住它，
農夫和牛都位于數軸上，農夫起始位于點 N，牛位于點 K，
農夫有兩種移動方式：
- 從 X 移動到 X?1 或 X+1，每次移動花費一分鐘
- 從 X 移動到 2?X，每次移動花費一分鐘
假設牛沒有意識到農夫的行動，站在原地不動，
農夫最少要花多少時間才能抓住牛？
輸入格式
共一行，包含兩個整數N和K，
輸出格式
輸出一個整數，表示抓到牛所花費的最少時間，
資料范圍
0≤N,K≤105
輸入樣例：
5 17輸出樣例：
4
思路：
題目講述一共有3種移動情況且權重一致（都為1）
- 從
X移動到X?1 - 從
X移動到X+1 - 從
X移動到2?X
相當于X 與X - 1,X + 1,2 * X ,各連一條邊,從n開始進行bfs到k，dist[k]表示k點到n點的最短距離
【代碼實作】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
queue<int> q;
int d[N];
int n, k;
int bfs()
{
memset(d, -1, sizeof d);
q.push(n);
d[n] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
if(t == k) return d[k];
if(t + 1 < N && d[t + 1] == -1)//在范圍內 且未被訪問
{
d[t + 1] = d[t] + 1;
q.push(t + 1);
}
if(t - 1 >= 0 && d[t - 1] == -1)
{
d[t - 1] = d[t] + 1;
q.push(t - 1);
}
if(t * 2 < N && d[t * 2] == -1)
{
d[t * 2] = d[t] + 1;
q.push(t * 2);
}
}
return - 1;
}
int main()
{
cin >> n >> k;
cout << bfs();
return 0;
}
三、總結
學習內容參考：
百度百科
acwing演算法基礎課、提高課
注：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/417088.html
標籤：其他
上一篇：一些編程實踐總結