引水入城

DFS+贪心覆盖

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
int n,m,now;
int g[N][N],vis[N][N];
pair<int,int> pos[N];

void dfs(int x,int y,int st){
  vis[x][y]=1;
  if(x==n-1&&st){                                //如果有多个城市肯定是连续的
    pos[now].first=min(pos[now].first,y);   
    pos[now].second=max(pos[now].second,y);
  }
  if (x>=1&&!vis[x-1][y]&&g[x][y]>g[x-1][y])     //不超出边界&&无标记&&连通性
    dfs(x-1,y,st);
  if (x<n-1&&!vis[x+1][y]&&g[x][y]>g[x+1][y])
    dfs(x+1,y,st);
  if (y>=1&&!vis[x][y-1]&&g[x][y]>g[x][y-1])
    dfs(x,y-1,st);
  if (y<m-1&&!vis[x][y+1]&&g[x][y]>g[x][y+1])
    dfs(x,y+1,st);
}

signed main(){                                   //头文件声明#define int long long，防止爆int
  cin>>n>>m;
  for(int i=0;i<n;i++)                           //读取地图
    for(int j=0;j<m;j++)
      cin>>g[i][j];

  //对于没有答案时的处理
  for(int i=0;i<m;i++)                           //靠近湖泊的城市测试与沙漠附近城市的连通性
    dfs(0,i,0);
  int ans=0;
  for(int i=0;i<m;i++)
    if (!vis[n-1][i])
      ans++;
  if(ans){
    cout<<0<<endl<<ans;                          //几座干旱区中的城市不可能建有水利设施
    return 0;
  }
  //遍历每座靠近湖泊的座城市，能覆盖到哪些城市
  for(int i=0;i<m;i++){
    memset(vis,0,sizeof(vis));//初始化0
    now=i;
    pos[now].first=501; //M-max：500
    if(n==1)                                     //特判只有一行的情况时
      dfs(0,i,1);
    else if(g[0][i]>g[1][i])
      dfs(1,i,1);
  }

  int maxx;
  now=-1;
  //选择最少区间覆盖整个区间的贪心问题
  while(now<m-1){ 
    maxx=-1;
    for(int i=0;i<m;i++)                         //贪心法：从左开始
      if(pos[i].first<=now+1&&pos[i].second>maxx)
      maxx=pos[i].second;
    ans++;                                       //建一座蓄水厂
    now=maxx;
  }
  cout<<1<<endl<<ans;//最少建造几个蓄水厂
  return 0;
}

笔记：题意的地势的要求用洪水填充寻找答案是很合适的，在有解的情况下尽可能少建蓄水厂，每个连通的范围肯定不可能交叉不连续，所以用贪心法来填充沙漠附近的城市