扩散
题目 扩散
思路分析
bfs，dfs好像都可以做
用bfs吧 因为有点像那个多源bfs的板子
很多坑
第一 做2020轮结束 无法每拓展一个点就增加一轮 因为多源 很多是同时做的
这个问题 可以用多传一个参数 表示该点是第几轮来解决
第二 地图是无限大的 一开始想着从0,0到1e4,1e4表示地图 标记过后遍历整个地图看有多少个ture就是答案 其实不然 还可能是-,-的坐标 地图的左下角并不是0,0 但是 我们数组的下标不能为负数 所以 用st标记是不可行的
这个问题 换由hash解决 此外 某点合法的判断也不再需要了 判断≥0 ≤n-1反而错误 因为真实的范围可能为负
unordered_map<int, unordered_map<int, bool>> visited; 是一个嵌套的无序映射结构，用于存储二维平面上的访问状态。以下是对这个结构的详细解释：
-
unordered_map：
- unordered_map 是 C++ 标准库提供的哈希表实现，它通过哈希函数提供常数时间复杂度的插入和查找操作。与 map 不同，unordered_map 不保证元素的顺序。
-
嵌套的 unordered_map：
- 外层的 unordered_map<int, unordered_map<int, bool>> 使用整数键来映射到内层的 unordered_map。外层的整数键代表二维平面中的 x 坐标。
- 内层的 unordered_map<int, bool> 使用整数键代表 y 坐标，并且其值为布尔类型，表示该位置是否被访问过。
-
用途：
- 这个嵌套结构允许动态地处理和存储任意大的二维平面访问状态，而不需要预先分配大块的内存。它只在访问到某个特定位置时才分配内存，从而节省了空间。
- 例如，如果我们访问了坐标 (3, 5)，那么 visited[3][5] 会被设置为 true，表示该位置已经被访问过。
-
优点：
- 避免了使用大块连续内存的需求，尤其在处理大范围的二维平面时非常有用。
- 提供了灵活性，可以处理非常稀疏的访问数据，而不会浪费不必要的内存。
考虑使用 pair当键 bool当值 但是std::unordered_map 默认使用 std::hash 来进行哈希计算，而 std::hash
对于 std::pair<int, int> 没有特化版本。要这样写的话 需要我们自己定义一个特化版本的 std::hash。反而更麻烦
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
typedef pair<PII,int> PPI;
const int N=1e4;
const int MAX_TIME=2020;
unordered_map<int, unordered_map<int, bool>> st;
queue<PPI> q;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y,int t){
return !st[x][y] && t<=MAX_TIME;
}
void bfs(){
while(!q.empty()){
auto cur=q.front();q.pop();
int ux=cur.first.first,uy=cur.first.second,t=cur.second;
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny,t+1)){
q.push({{nx,ny},t+1});
st[nx][ny]=true;
}
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
q.push({{0,0},0});
st[0][0]=true;
q.push({{2020,11},0});
st[2020][11]=true;
q.push({{11,14},0});
st[11][14]=true;
q.push({{2000,2000},0});
st[2000][2000]=true;
bfs();
int cnt=0;
for(auto row:st){
for(auto col:row.second){
if(col.second)
cnt++;
}
}
cout<<cnt;
return 0;
}
💬 评论