社区讨论
C++12分求助
P2919[USACO08NOV] Guarding the Farm S参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lvb0pyma
- 此快照首次捕获于
- 2024/04/22 21:53 2 年前
- 此快照最后确认于
- 2024/04/23 13:28 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
int a[706][706];
bool vis[706][706];
const int dx[8]={1,-1,0,0,1,1,-1,-1};
const int dy[8]={0,0,1,-1,-1,1,1,-1};
void dfs(int x,int y,int cnt,int high){
//当前在(x,y),要染成cnt色,能染的海拔<=high
for(int i = 0;i < 4;++i){
int xx=x+dx[i];
int yy=y+dy[i];
int xz_h=a[x][y],next_h=a[xx][yy];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]!=0){
if(next_h>xz_h){
high=next_h;
}
a[xx][yy]=cnt;
vis[xx][yy]=true;
dfs(xx,yy,cnt,high);
}
}
for(int i = 4;i < 8;++i){
int xx=x+dx[i];
int yy=y+dy[i];
if(i==4){
if(a[xx][yy+1]==0&&a[xx-1][yy]==0) continue;
}
if(i==5){
if(a[xx][yy-1]==0&&a[xx-1][yy]==0) continue;
}
if(i==6){
if(a[xx+1][yy]==0&&a[xx][yy-1]==0) continue;
}
if(i==8){
if(a[xx+1][yy]==0&&a[xx][yy+1]==0) continue;
}
int xz_h=a[x][y],next_h=a[xx][yy];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]!=0){
if(next_h>xz_h){
high=next_h;
}
a[xx][yy]=cnt;
vis[xx][yy]=true;
dfs(xx,yy,cnt,high);
}
}
return;
}
int main(){
cin>>n>>m;
memset(vis,false,sizeof(vis));
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
cin>>a[i][j];
}
}
int c=-1;
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
if(!vis[i][j]&&a[i][j]!=0){
a[i][j]=c;
// cout << i << " " << j << "\n";
ans++;
vis[i][j]=true;
dfs(i,j,c,a[i][j]);
c--;
}
}
}
/* for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
cout << a[i][j] << " ";
}
cout << "\n";
}*/
cout << ans;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...