2 条题解
-
1
set,vector都可以 暂时存走了哪些点都可以都可 然后把走过的点赋值上ans if(jz[x][y]==0)判断走没走过优化避免重复计算值 其他的就是vector用法
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,ans; char a[1005][1005]; bool pd[1005][1005]; ll jz[1005][1005]; vector<pair<ll,ll>>b; void dfs(int x,int y,char syg) { if(jz[x][y]!=0||pd[x][y]==true|| x<1||x>n|| y<1||y>n|| syg==a[x][y]) return; pd[x][y]=true; ans++; b.push_back(make_pair(x,y)); dfs(x+1,y,a[x][y]); dfs(x-1,y,a[x][y]); dfs(x,y+1,a[x][y]); dfs(x,y-1,a[x][y]); return; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m;; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; while(m--) { ll x,y; cin>>x>>y; if(jz[x][y]==0) { dfs(x,y,'a'); for (auto&i:b) jz[i.first][i.second]=ans; b.clear(); ans=0; } printf("%lld\n",jz[x][y]); } return 0; }
信息
- ID
- 1095
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 58
- 已通过
- 4
- 上传者