kuangbin专题 专题一 简单搜索 Oil Deposits HDU - 1241
2024-09-28 07:34:23
题目链接: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 ;
}
最新文章
- SCI英文论文写作- Latex 进阶
- C++继承和多态
- ACM/ICPC 之 四道MST-Prim解法(POJ1258-POJ1751-POJ2349-POJ3026)
- function 类型
- Vue.js相关知识1
- layoutSubviews 浅尝
- oracle OVER(PARTITION BY) 函数
- Java异常的一个小知识
- 详细解读Jquery各Ajax函数:$.get(),$.post(),$.ajax(),$.getJSON() —(转)
- zoj3471(状压dp)
- [ExtJS5学习笔记]第22 Extjs5正在使用beforeLabelTpl添加所需的配置选项标注星号标记
- java中final小结
- ci框架中表前缀的处理
- SSH连不上虚拟机的问题解决
- 关于 jar 包数据更新的问题
- 【51】java设计模式-工厂设计模式剖析
- PowerShell 中 RunspacePool 执行异步多线程任务
- java 利用jsoup 爬取知乎首页问题
- springboot的maven配置问题
- 开机自动启动WEB服务,共享目录。
热门文章
- 在IOS开发中使用GoogleMaps SDK
- WPF MVVM+EF 增删改查 简单示例(一)
- MVVM 下 ContextMenu的命令绑定
- vs2017 js cordova + dotnet core 开发app
- centos 6.5 搭建ftp 服务器(vsftpd的配置文件说明)
- 利用NPOI生成DOCX文档
- .gitignore 配置后无效
- UWP中弹出框屏幕适配问题
- ML:吴恩达 机器学习 课程笔记(Week9~10)
- 关于跨进程使用回调函数的研究:以跨进程获取Richedit中RTF流为例(在Delphi 初始化每一个TWinControl 对象时,将会在窗体 的属性(PropData)中加入一些标志,DLL的HInstance的值与HOST 进程的HInstance并不一致)