C++描述 1113. 紅與黑
??大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客 ，同時正在嘗試在B站中做一些內容分享，B站主頁為： 亓官劼的B站主頁
本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
若需聯系博主，可以聯系本人微信：qiguanjie2015
題目
有一間長方形的房子，地上鋪了紅色、黑色兩種顏色的正方形瓷磚，
你站在其中一塊黑色的瓷磚上，只能向相鄰（上下左右四個方向）的黑色瓷磚移動，
請寫一個程式，計算你總共能夠到達多少塊黑色的瓷磚，
輸入格式
輸入包括多個資料集合，
每個資料集合的第一行是兩個整數 W 和 H，分別表示 x 方向和 y 方向瓷磚的數量，
在接下來的 H 行中，每行包括 W 個字符，每個字符表示一塊瓷磚的顏色，規則如下
1）‘.’：黑色的瓷磚；
2）‘#’：紅色的瓷磚；
3）‘@’：黑色的瓷磚，并且你站在這塊瓷磚上，該字符在每個資料集合中唯一出現一次，
當在一行中讀入的是兩個零時，表示輸入結束，
輸出格式
對每個資料集合，分別輸出一行，顯示你從初始位置出發能到達的瓷磚數(記數時包括初始位置的瓷磚)，
資料范圍
1≤W,H≤20
輸入樣例：
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
輸出樣例：
45
題解思路
這里即求從@位置開始，最大連續的.的數量，這里有三種方法來解決：BFS、DFS、并查集，這里提供BFS和DFS的解法實作，并查集的實作也非常簡單，大家可以自行實作，
如果是使用BFS來實作的話，那么就是一層一層的來查找一圈是否可以擴展，如果可以擴展，則加入待擴展佇列，使用res來記錄最大連通數，每次取待擴展結點時，res++，直到所有結點都擴展完畢，待擴展佇列為空時，獲得當前最大連通數，
BFS實作
#include<iostream>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n,m;
typedef pair<int, int> PII;
// 存盤輸入資料
char g[25][25];
int bfs(int sx,int sy){
int res = 0;
queue<PII> q;
// 當前位置加入佇列
q.push({sx,sy});
g[sx][sy] = '$';// 設定為訪問過
// 方向偏移量
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
while(q.size()){
// 出隊一個帶擴展結點，res++
auto t = q.front();
q.pop();
// 記錄可擴展數
res++;
for(int i = 0 ; i < 4; i++){
int a = t.x + dx[i], b = t.y + dy[i];
// 當前不可擴展時，直接continue
if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] != '.')
continue;
else{
g[a][b] = '$';// 設定為訪問過
q.push({a,b});// 加入待擴展佇列
}
}
}
return res;
}
int main(){
while(cin>>m>>n , n || m){
for (int i = 0; i < n; i ++ ) cin >> g[i];
int x,y;
for(int i = 0; i < n; i++){
for(int j = 0 ; j < m; j++){
// 找到當前位置
if(g[i][j] == '@'){
x = i;
y = j;
}
}
}
// 通過bfs搜索，回傳結果
cout<<bfs(x,y)<<endl;
}
return 0;
}
DFS實作
dfs實作更簡短，但是會有爆堆疊的風險，
#include<iostream>
using namespace std;
int n,m;
// 存盤輸入資料
char g[25][25];
// 方向偏移量
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
int dfs(int x,int y){
int res = 1;
g[x][y] = '$';//使用`$`標記為訪問過
// 查看上、下、左、右四個方向
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] == '.'){
res += dfs(a,b);
}
}
return res;
}
int main(){
while(cin>>m>>n , n || m){
for (int i = 0; i < n; i ++ ) cin >> g[i];
int x,y;
for(int i = 0; i < n; i++){
for(int j = 0 ; j < m; j++){
// 找到當前位置
if(g[i][j] == '@'){
x = i;
y = j;
}
}
}
// 通過bfs搜索，回傳結果
cout<<dfs(x,y)<<endl;
}
return 0;
}
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248991.html
標籤：其他
上一篇：【劍指Offer】輸入一個鏈表，按鏈表從尾到頭的順序回傳一個ArrayList
下一篇：曝光，程式員的 10 個摸魚神器