点击打开链接
题目意思:给你一块区域里面分布着油田,只要有连着就属于同一个油田,求出该区域有几个油田
解题思路:简单的Bfs 或 dfs 可以搞定 ,注意对走过的进行标记用mark数组。
代码:
//DFS代码(用到递归)
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 110;
int n , m , sum;
char ch[MAXN][MAXN];
int mark[MAXN][MAXN];//标记是否走过
int x[8] = {-1,-1,0,1,1,1,0,-1};//方向数组
int y[8] = {0,1,1,1,0,-1,-1,-1};
//搜索
void dfs(int i , int j){
if(mark[i][j] == 1)
return;
for(int k = 0 ; k < 8 ; k++){
if(i+x[k]<0 || i+x[k]>=m || j+y[k]<0 || j+y[k]>=n)//越界
continue;
if(ch[i+x[k]][j+y[k]] == '*')//没用的字符
continue;
if(ch[i+x[k]][j+y[k]] == '@'){//继续下一步递归
mark[i][j] = 1;
dfs(i+x[k] , j+y[k]);
}
}
}
//处理问题函数
void solve(){
int i , j;
sum = 0;
memset(mark , 0 , sizeof(mark));
for(i = 0 ; i < m ; i++){
for(j = 0 ; j < n ; j++){
if(ch[i][j] == '@' && mark[i][j] == 0){
sum++;
dfs(i , j);
}
}
}
cout<<sum<<endl;
}
//主函数
int main(){
while(scanf("%d%d%*c" , &m , &n) && m && n){
for(int i= 0 ; i < m ; i++){
for(int j= 0 ; j < n ; j++)
scanf("%c" , &ch[i][j]);
getchar();
}
solve();
}
}
//BFS代码(用到队列)
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 110;
int n , m , sum;
char ch[MAXN][MAXN];
int mark[MAXN][MAXN];
int x[8] = {-1,-1,0,1,1,1,0,-1};
int y[8] = {0,1,1,1,0,-1,-1,-1};
queue<char>q;
//广搜
void Bfs(int i , int j){
if(q.empty()|| mark[i][j] == 1)
return;
if(!q.empty()){
for(int k = 0 ; k < 8 ; k++){
if(i+x[k]<0 || i+x[k]>=m || j+y[k]<0 || j+y[k]>=n)
continue;
if(ch[i+x[k]][j+y[k]] == '*')
continue;
if(ch[i+x[k]][j+y[k]] == '@'){
q.pop();//第一个出对
q.push('@');//入对
mark[i][j] = 1;
Bfs(i+x[k] , j+y[k]);//可以这里去掉在外面改为while循环
}
}
}
}
//处理问题函数
void solve(){
int i , j;
sum = 0;
memset(mark , 0 , sizeof(mark));
for(i = 0 ; i < m ; i++){
for(j = 0 ; j < n ; j++){
if(ch[i][j] == '@' && mark[i][j] == 0){
sum++;
q.push('@');
Bfs(i , j);
}
}
}
cout<<sum<<endl;
}
//主函数
int main(){
while(scanf("%d%d%*c" , &m , &n) && m && n){
for(int i= 0 ; i < m ; i++){
for(int j= 0 ; j < n ; j++)
scanf("%c" , &ch[i][j]);
getchar();
}
solve();
}
}
分享到:
相关推荐
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
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 ...
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
Systematics of Sulfur and Carbon Isotopes in Hydrothermal__ Ore Deposits
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...
以太坊2存款合约子图 这是Onyx的以太坊2存款合约子图。 例如,要查询存款以获取特定的验证者公钥: curl \ --data '{"query": "{... https://api.thegraph.com/subgraphs/name/attestantio/eth2deposits-onyx
这是由美联储经济数据库 (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项目源码、...