https://www.luogu.org/problemnew/show/P1514

題解：

BFS+排序+剪枝

對第一行的數(shù)據(jù)排序

按從大到小的順序進行BFS，記錄全部已經(jīng)走過的格子和當前出發(fā)點可以走過的格子，記錄當前出發(fā)點最后在最后一行的狀態(tài)

因為可以證明區(qū)間一定連續(xù)。所以記錄左右端點

然后最后一行不斷暴力查找當前點為左端點的最大區(qū)間，直到完全覆蓋

答案不存在時，暴力枚舉最后一行是否有不能覆蓋的點

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=500+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k; int ans,cnt,flag,temp; int a[N][N]; int b[][2]={1,0,0,1,-1,0,0,-1}; int vis[N][N]; int viss[N][N]; char str; int l[N],r[N]; struct node {int v;int x,y;bool operator <(const node &S)const{return v>S.v;} }e[N]; struct Node {int x,y; }s,tmp,f; void bfs(int x,int y){queue<Node>q;s.x=x;s.y=y;q.push(s);memset(vis,0,sizeof(vis));vis[s.x][s.y]=1;viss[s.x][s.y]=1;while(!q.empty()){f=q.front();q.pop();//cout<<f.x<<f.y<<endl;for(int i=0;i<4;i++){tmp.x=f.x+b[i][0];tmp.y=f.y+b[i][1];if(0<tmp.x&&tmp.x<=n&&0<tmp.y&&tmp.y<=m&&!vis[tmp.x][tmp.y]&&a[f.x][f.y]>a[tmp.x][tmp.y]){vis[tmp.x][tmp.y]=1;viss[tmp.x][tmp.y]=1;q.push(tmp);}}} } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d%d",&n,&m);//scanf("%d",&t);//while(t--){}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}cnt=0;for(int i=1;i<=m;i++){e[i].v=a[1][i];e[i].x=1;e[i].y=i;}sort(e+1,e+m+1);for(int i=1;i<=m;i++){if(!viss[e[i].x][e[i].y]){bfs(e[i].x,e[i].y);//cout<<e[i].y<<" "<<r[i]<<" ";for(int j=1;j<=m;j++){if(vis[n][j]){l[i]=j;break;}}for(int j=1;j<=m;j++){if(vis[n][j]){r[i]=j;}}}}flag=1;cnt=0;for(int j=1;j<=m;j++){if(!viss[n][j]){flag=0;cnt++;}}cout << flag << endl;if(flag){int left=1;while (left<=m){int maxr=0;for (int i=1;i<=m;i++)if (l[i]<=left)maxr=max(maxr,r[i]);ans++;left=maxr+1;//cout<<left;}cout << ans << endl;}else{cout << cnt << endl;}//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的引水入城的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。