紅與黑問題

前言

獻給阿爾吉儂的花束( 入門級bfs查找 + 模版解讀 + 錯誤示范
在之前的博客當中，詳細地介紹了這類題目的解法，今天為大家?guī)硪坏李愃频念}目練練手，后續(xù)還會更新更有挑戰(zhàn)的題目以及更為詳細的解析，喜歡的小伙伴可以點個關(guān)注啦！

問題描述

有一間長方形的房子，地上鋪了紅色、黑色兩種顏色的正方形瓷磚。

你站在其中一塊黑色的瓷磚上，只能向相鄰（上下左右四個方向）的黑色瓷磚移動。

請寫一個程序，計算你總共能夠到達多少塊黑色的瓷磚。

輸入格式
輸入包括多個數(shù)據(jù)集合。

每個數(shù)據(jù)集合的第一行是兩個整數(shù) W 和 H，分別表示 x 方向和 y 方向瓷磚的數(shù)量。

在接下來的 H 行中，每行包括 W 個字符。每個字符表示一塊瓷磚的顏色，規(guī)則如下

1）‘.’：黑色的瓷磚；
2）‘#’：紅色的瓷磚；
3）‘@’：黑色的瓷磚，并且你站在這塊瓷磚上。該字符在每個數(shù)據(jù)集合中唯一出現(xiàn)一次。

當在一行中讀入的是兩個零時，表示輸入結(jié)束。

輸出格式
對每個數(shù)據(jù)集合，分別輸出一行，顯示你從初始位置出發(fā)能到達的瓷磚數(shù)(記數(shù)時包括初始位置的瓷磚)。

數(shù)據(jù)范圍
1≤W,H≤20
輸入樣例：

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

輸出樣例：

45

bfs 解法

話不多說，直接上代碼，解析都在注釋當中：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 23;
char g[N][N];
int h,w,ans;
typedef pair<int,int> PII;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs(int x,int y){g[x][y]='#';queue<PII> q;q.push({x,y});//隊列的初始化while(!q.empty()){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<=h && b>=1 && b<=w && g[a][b]=='.'){q.push({a,b});ans++;g[a][b]='#';//把走過的路封死//防止重讀走的現(xiàn)象}}}
}
int main(){while(cin>>w>>h,w||h){//注意這里的輸入//寬和高要反著來int x,y;ans=0;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cin>>g[i][j];if(g[i][j]=='@'){x=i,y=j;//找到其實方塊}}}bfs(x,y);cout<<ans+1<<endl;//為什么要 +1 呢？//因為后續(xù)的bfs算法沒有考慮最開始的那個方塊}
}

dfs 解法

#include<iostream>
using namespace std;
const int N =23;
char g[N][N];
int ans,h,w;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){g[x][y]='#';for(int i=0;i<4;i++){int a=x+dx[i];int b=y+dy[i];if(x>=1 && x<= h && y>=1 && y<=w && g[a][b]=='.'){dfs(a,b);ans++;}}
}
int main(){while(cin>>w>>h,w||h){ans=0;int x,y;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cin>>g[i][j];if(g[i][j]=='@'){x=i,y=j;}}}dfs(x,y);cout<<ans+1<<endl;}return 0;
}