题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=513
样例输入:
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
样例输出:
0
1
2
2
分析:
这一题可以说是搜索中最基础的一题之一。 要找出相连在一起的有多少块, 因此, 依次枚举,遇到@时就进行搜索,用深搜,广搜都行,目的是把相连的@都标记为已访问。
下面给出用DFS(深搜)和BFS(广搜)的代码。
代码1: DFS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n;
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},
{ 1,0},{1,-1},{0,-1},{-1,-1}};
bool vis[105][105];
char map[105][105];
void dfs(int x, int y){
for(int i=0; i<8; ++i){
int dx=x+dir[i][0], dy=y+dir[i][1];
if(dx>=0 && dx<m && dy>=0 && dy<n && map[dx][dy]=='@' && !vis[dx][dy]){
vis[dx][dy] = true;
dfs(dx, dy);
}
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int i,j;
while(scanf("%d %d%*c",&m,&n) && m && n){
for(i=0; i<m; ++i)
gets(map[i]);
memset(vis, 0, sizeof(vis));
int cnt=0;
for(i=0; i<m; ++i){
for(j=0; j<n; ++j){
if(map[i][j]=='@' && !vis[i][j]){
++cnt;
dfs(i, j);
}
}
}
printf("%d\n",cnt);
}
return 0;
}
代码2:
以上是用递归的方式进行DFS,但是如果数据量很大, 递归方式有可能栈溢出的危险!
下面是模拟栈的方式,而不是递归的方式写DFS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int m,n;
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},
{ 1,0},{1,-1},{0,-1},{-1,-1}};
bool vis[105][105];
char map[105][105];
struct Node{ int x,y; };
stack<Node>st;
void dfs(int x, int y){
while(!st.empty()) st.pop();
Node temp;
temp.x = x, temp.y = y;
st.push(temp);
while(!st.empty()){
temp = st.top();
st.pop();
for(int i=0; i<8; ++i){
int dx=temp.x+dir[i][0], dy=temp.y+dir[i][1];
if(dx>=0 && dx<m && dy>=0 && dy<n && map[dx][dy]=='@' && !vis[dx][dy]){
vis[dx][dy] = true;
Node t;
t.x = dx, t.y = dy;
st.push(t);
}
}
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int i,j;
while(scanf("%d %d%*c",&m,&n) && m && n){
for(i=0; i<m; ++i)
gets(map[i]);
memset(vis, 0, sizeof(vis));
int cnt=0;
for(i=0; i<m; ++i){
for(j=0; j<n; ++j){
if(map[i][j]=='@' && !vis[i][j]){
++cnt;
dfs(i, j);
}
}
}
printf("%d\n",cnt);
}
return 0;
}
代码3: BFS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n;
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},
{ 1,0},{1,-1},{0,-1},{-1,-1}};
bool vis[105][105];
char map[105][105];
struct Node{ int x,y; };
Node que[10000];
void bfs(int x,int y){
int front=0, rear=1;
que[0].x = x;
que[0].y = y;
while(front < rear){
Node t=que[front++];
for(int i=0; i<8; ++i){
int dx=t.x+dir[i][0], dy=t.y+dir[i][1];
if(dx>=0 && dx<m && dy>=0 && dy<n && map[dx][dy]=='@' && !vis[dx][dy]){
vis[dx][dy] = true;
Node temp;
temp.x = dx, temp.y = dy;
que[rear++] = temp;
}
}
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int i,j;
while(scanf("%d %d%*c",&m,&n) && m && n){
for(i=0; i<m; ++i)
gets(map[i]);
memset(vis, 0, sizeof(vis));
int cnt=0;
for(i=0; i<m; ++i){
for(j=0; j<n; ++j){
if(map[i][j]=='@' && !vis[i][j]){
++cnt;
bfs(i, j);
}
}
}
printf("%d\n",cnt);
}
return 0;
}
分享到:
相关推荐
Laravel开发-deposits Laravel存款
We are glad to know that our paper “Review of research in internal-wave and internal-tide deposits of China” (Gao et al., 2013) published in Journal of Palaeogeography has attracted close attention ...
This discussion of a review article by Gaoet al. (2013), published in theJournalof Palaeogeography (2(1): 56-65), is aimed at illustrating that interpretations of ten ancient ex-amples in China and ...
这是由美联储经济数据库(FRED)托管的美联储数据集。M2的小面额定期存款部分包括银行定期存款和余额不到100,000美元的储蓄帐户。M2的小面额定期存款部分不包括个人退休账户(IRA)和Keogh存款机构的余额,因为退休...
abnormal white-yellow deposits on the retina. Segmentation of these features using conventional image analysis methods is quite complicated mainly due to the non-uniform illumination and the ...
formation of gold deposits.pdf,形成与成因,分布与产状
这是由美联储经济数据库(FRED)托管的美联储数据集。FRED有一个数据平台,它们根据数据更新的频率来更新其信息。 TCD.csv TCDSL.csv total-checkable-deposits_...total-checkable-deposits_metadata_1.json
这是由美联储经济数据库(FRED)托管的美联储数据集。...total-savings-deposits-at-all-depository-institutions_metadata.json total-savings-deposits-at-all-depository-institutions_metadata_1.json WSAVNS.csv
这是由美联储经济数据库 (FRED) 托管的美联储的数据集。此数据集每天更新。 GDTCBW.csv us-government-deposits-total-cash-balance_metadata.json
deposits-all-commercial-banks_metadata.json deposits-all-commercial-banks_metadata_1.json deposits-with-federal-reserve-banks-other-than-reserve-balances-u.s.-treasury-general-account_metadata.json ...
这是由美联储经济数据库(FRED)托管的美联储数据集。 savings-deposits-total_metadata.json SAVINGSL.csv
Gao and Eriksson (1991) firstly recognized the Ordovician internal-tide deposits of the Appalachians in the USA. Since then, Gao and many Chinese sedimentologists have discovered and studied 9 ...
Systematics of Sulfur and Carbon Isotopes in Hydrothermal__ Ore Deposits
--data '{"query": "{deposits(where:{validatorPubKey:\"0xa2fbaa9e4b454c672ff1e89cd70c5f5e84d7dfab9a3b011c12d56d6f3e56aef0a760ba3e7df78ed8f2783971ea54962a\"}){index amount withdrawalCredentials ...
The three most crucial factors for the formation of large and super-large magmatic sulfide deposits are: (1) a large volume of mantle-derived mafic-ultramafic magmas that participated in the formation...
这是由美联储经济数据库 (FRED) 托管的美联储的数据集。FRED有一个数据平台,他们根据数据更新的频率更新他们的信息。 TREASURY.csv treasury-deposits-with-federal-reserve-banks_metadata.json
OSL dating of loess deposits bracketing Sheep Creek tephra beds
M1的活期存款部分定义为商业银行和外国相关机构(美国政府、美国和外国存管机构以及外国官方机构除外)的活期存款总额。为了避免将同时存托机构账面上的存款重复...demand-deposits-total_metadata.json DEMDEPSL.csv
应用软硬酸碱理论解释岩浆热液矿床的成矿专属性,汪洋,焦永玲,从软硬酸碱(HASB)理论来看,热液矿床的成矿专属性是岩浆、成矿元素阳离子与热液中的阴离子受制于最大硬度原理和最小亲电性原理�
WooCommerce Deposits - Partial Payments Plugin Woocommerce Deposits - 部分付款插件" ---------- 泰森云每天更新发布最新WordPress主题、HTML主题、WordPress插件、shopify主题、opencart主题、PHP项目源码、...