洛谷P 1514引水入城

タイトルリンク
洛谷P 1514引水入城
問題解決の考え方:
検索と区間統合を総合的に考察した.難点は、最後の行区間の左右の端点を記録することです.また、最初の行から検索を開始する場合は、最適化に注意してください.最初の行の各列を起点として検索を開始するのではなく、左右の端点よりも大きな列から検索を開始することで、時間を節約できます.区間マージ注意ソート.

include <iostream>
#include
#include
#include
using namespace std;
const int maxv=233233233;
int map[510][510],vis[510][510];
int flag[510];
int g[][2]={-1,0,1,0,0,1,0,-1};//        
int n,m;
struct qujian{//   
	int l,r;
}c[510];
bool cmp(qujian A,qujian B){//    ，     
	if(A.l==B.l) return A.r<B.r;
	return A.l<B.l;
}
void dfs(int x,int y,int index){//  x，y，           index 
	if(x==n){
		c[index].l=min(c[index].l,y);//     
		c[index].r=max(c[index].r,y);
		flag[y]=1;
	}
	for(int i=0;i<4;i++){
		int nx=x+g[i][0];
		int ny=y+g[i][1];
		if(nx<1||nx>n||ny<1||ny>m) continue;
		if(!vis[nx][ny]&&map[x][y]>map[nx][ny]){
			vis[nx][ny]=1;
			dfs(nx,ny,index);
		}
	}
}
//int test(){
//	for(int i=1;i<=m;i++){
//		if(!vis[n][i]) return 1;//     
//	}
//	return 0;
//}
int main(int argc, char** argv) {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&map[i][j]);
			if(i==1) c[j].l=maxv;
		}
	} 
	
	for(int i=1;i<=m;i++){
		if(map[1][i]>=map[1][i-1]&&map[1][i]>=map[1][i+1]){//  1，                  
			memset(vis,0,sizeof(vis));
			dfs(1,i,i);
		}
	}
	
	int cnt=0;
	for(int j=1;j<=m;j++){
		if(!flag[j]) cnt++;//  flag[j]==0，       j       。 
	}
	if(cnt==0){
		sort(c+1,c+m+1,cmp);//   
		int len=m;
		while(c[m].l==maxv) --m;//          
//		for(int i=1;i<=m;i++)
//			printf("%d %d
",c[i].l,c[i].r);
		//         
		int i1=1,tr=1,ans=0;//     ，   ，    ans 
		while(tr<=len){
			int temp=0;
			while(c[i1].l<=tr){
				temp=max(temp,c[i1].r);
				i1++;
			} 
			tr=temp+1;
			ans+=1;
		} 
		printf("1
%d
",ans);
	}
	else{
		printf("0
%d
",cnt);
	}
	return 0;
}