题目大致意思就是说给你一个迷宫的地图,让你找到从每一个走不通的地方(*)旁边紧靠着的空地(.)的大小(最后要加上自己,也就是空地的数量加一)
很容易想到使用bfs或者dfs,这里我们就使用dfs遍历每个空地联通块,不能直接暴力记录,会超时,使用标号连通块加set的使用能够减少时间消耗
我做过这道 哈哈
这是我的原博客
https://blog.csdn.net/weixin_62403934/article/details/124605813?spm=1001.2014.3001.5501
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m;
int cnt;
int mp[N][N];
int ans[N*N]; //mp 该点所属连通块的标号, ans表示该连通块的大小
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //四个方向
void dfs(int x, int y){
mp[x][y]=cnt; //该点所属联通块的标号
ans[cnt]++; //该连通块的大小加一
for(int i=0 ; i<4 ; i++){
int xx=x+dx[i], yy=y+dy[i];
//超出范围 走不通 已经标号 都跳过下一次递归
if(xx>=n || xx<0 || yy>=m || yy<0 || g[xx][yy]=='*' || mp[xx][yy]!=0) continue;
dfs(xx, yy);
}
}
int main(){
cin>>n>>m;
for(int i=0 ; i<n ; i++) scanf("%s", g[i]);
for(int i=0 ; i<n ; i++)
for(int j=0 ; j<m ; j++){
if(g[i][j] == '.' && mp[i][j]==0){
//每次遇到空的地,标号加一
cnt++;
dfs(i, j);
}
}
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
if(g[i][j] == '*'){
//set去重
set<int> st;
set<int>::iterator it;
int re=0;
for(int k=0 ; k<4 ; k++){
int xx=i+dx[k], yy=j+dy[k];
if(xx>=n || xx<0 || yy>=m || yy<0 || g[xx][yy]=='*') continue;
//将每个点所属连通块的标号放入set
st.insert(mp[xx][yy]);
}
for(it=st.begin() ; it!=st.end() ; it++) re+=ans[*it];
cout<<(re+1)%10;
}
else cout<<".";
}
cout<<endl;
}
return 0;
}
泪目 我把unordered_map换成set就过了 不换就死活被卡 大佬%%%
这是啥意思
通过迭代器遍历
大佬,问一下为什么我这里用unordered_set反而还会超时呢?不是unordered_set比set效率更高吗?
哈哈哈 我也不是很清楚捏 我一般就用的set
好的,谢谢大佬
#《卡$hash$》
大佬,我不是很懂。可以说的具体一点吗?
https://www.cnblogs.com/Hs-black/p/12219270.html
thanks。
哈希的期望时间复杂度是$O(1)$,每个数会通过取模放到相应的位置,但是有取到同一个位置上的情况,这时时间复杂度就会高。因为$unordered$_$set$有固定的哈希函数,出题人有可能会卡$hash$,把每一个数都取到同一个点上,这样时间复杂度就会从$O(1)$变成O$(n)$。
哦,懂了,所以set有时候会更好是吧?大佬。
我还是建议用$unordered$_$set$,你可以自己写一个哈希函数,这样既保证了效率又不会被出题人卡
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=1e6+10,M=1010;
char tu[M][M];
int p[N],cnt[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i){
scanf(“%s”,tu[i]+1);
}
for(int i=1;i<=n*m;i) {
p[i]=i;
cnt[i]=1;
}
for(int i=1;i<=n;i){
for(int j=1;j<=m;j){
if(tu[i][j]==’.’){
for(int k=0;k<2;k){//枚举下和右;
int a=i,b=j;
a+=dx[k];b+=dy[k];
if(a<=n&&b<=m&&tu[a][b]==’.’){
int x=find((i-1)m+j),y=find((a-1)m+b);
if(x!=y){
p[x]=y;
cnt[y]+=cnt[x];
}
}
}
}
}
}
for(int i=1;i<=n;i){
for(int j=1;j<=m;j){
if(tu[i][j]==’.’) printf(“.”);
else{
//int tt[4],bn[4];
unordered_map[HTML_REMOVED] m1;
for(int k=0;k<4;k){
int a=i,b=j;
a+=dx[k];b+=dy[k];
if(a>=1&&a<=n&&b>=1&&b<=m&&tu[a][b]==’.’){
int y=find((a-1)m+b);
m1[y]++;
if(m1[y]==1){
cnt[(i-1)m+j]+=cnt[y];
}
}
}
printf(“%d”,cnt[(i-1)*m+j]%10);
}
}
printf(“\n”);
}
return 0;
}
我这哪里慢了?
## 这是只有c++才能过的去吗?我这是哪里写慢了?
试试快速输入输出 Java输入超过1e5就不行了
谢谢大佬,终于过了。。
大意了,超时了
卧槽,我也是这思路,但是没在dfs过程中把这些点标号,超时了....大佬这写法太可了
hh 我也是学的别人的方法后自己学会的 加油~