题目链接:https://vjudge.net/problem/HDU-1241

题意:问有几个油田,一个油田由相邻的‘@’,组成。

思路:bfs,dfs都可以,只需要遍历地图,遇到‘@’,跑一遍搜索,标记跑过的点,然后油田数+1.


 #include <iostream>
#include <cstring>
#include<vector>
#include<string>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std; #define inf (1LL << 31) - 1
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
int mv[][] = { { , }, { , - }, { , }, { -, },
{ , }, { -, - }, { -, }, { , - } };
char mp[N][N];
bool vis[N][N];
int n, m; struct node{
int x, y;
}; inline void init(){
rep(i, , n) rep(j, , m) vis[i][j] = false;
} inline void input(){ init();
rep(i, , n) rep(j, , m) cin >> mp[i][j];
} inline bool check(int x, int y){
return x >= && x <= n && y >= && y <= m;
} void bfs(int now_x, int now_y){ vis[now_x][now_y] = true; queue<node> que;
que.push(node{ now_x, now_y }); while (!que.empty()){ node tmp = que.front();
que.pop(); rep__(p, , ){
int dx = tmp.x + mv[p][];
int dy = tmp.y + mv[p][]; if (check(dx, dy) && !vis[dx][dy] && mp[dx][dy] == '@'){
vis[dx][dy] = true;
que.push(node{ dx, dy });
}
}
}
} void work(){ int ans = ; rep(i, , n) rep(j, , m){
//附加条件,这个‘@’没被访问过,说明是新的油田的一部分
if (mp[i][j] == '@' && !vis[i][j]){
bfs(i, j);
++ans;
}
} cout << ans << endl;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); while (cin >> n >> m){ if (m == ) break; input();
work();
} return ;
}

最新文章

  1. SCI英文论文写作- Latex 进阶
  2. C++继承和多态
  3. ACM/ICPC 之 四道MST-Prim解法(POJ1258-POJ1751-POJ2349-POJ3026)
  4. function 类型
  5. Vue.js相关知识1
  6. layoutSubviews 浅尝
  7. oracle OVER(PARTITION BY) 函数
  8. Java异常的一个小知识
  9. 详细解读Jquery各Ajax函数:$.get(),$.post(),$.ajax(),$.getJSON() —(转)
  10. zoj3471(状压dp)
  11. [ExtJS5学习笔记]第22 Extjs5正在使用beforeLabelTpl添加所需的配置选项标注星号标记
  12. java中final小结
  13. ci框架中表前缀的处理
  14. SSH连不上虚拟机的问题解决
  15. 关于 jar 包数据更新的问题
  16. 【51】java设计模式-工厂设计模式剖析
  17. PowerShell 中 RunspacePool 执行异步多线程任务
  18. java 利用jsoup 爬取知乎首页问题
  19. springboot的maven配置问题
  20. 开机自动启动WEB服务,共享目录。

热门文章

  1. 在IOS开发中使用GoogleMaps SDK
  2. WPF MVVM+EF 增删改查 简单示例(一)
  3. MVVM 下 ContextMenu的命令绑定
  4. vs2017 js cordova + dotnet core 开发app
  5. centos 6.5 搭建ftp 服务器(vsftpd的配置文件说明)
  6. 利用NPOI生成DOCX文档
  7. .gitignore 配置后无效
  8. UWP中弹出框屏幕适配问题
  9. ML:吴恩达 机器学习 课程笔记(Week9~10)
  10. 关于跨进程使用回调函数的研究:以跨进程获取Richedit中RTF流为例(在Delphi 初始化每一个TWinControl 对象时,将会在窗体 的属性(PropData)中加入一些标志,DLL的HInstance的值与HOST 进程的HInstance并不一致)