70分广搜代码求调
查看原帖
70分广搜代码求调
774561
Xiao_zhiwen楼主2024/8/16 15:28

捕获.PNG

#include <bits/stdc++.h>
using namespace std;
const int N=110,M=-1e9;
typedef pair<int,int>PII;
int r,c,a[N][N],f[N][N],ans=M;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
void bfs(int i,int j){//广搜
	queue<PII> q;
	memset(f,-1,sizeof(f));
	q.push(make_pair(i,j));
    f[i][j]=1;
    while(!q.empty()){
    	int t1,t2;
    	t1=t2=0;
    	PII u=q.front();
    	q.pop();
    	for(int v=0;v<4;v++){//在上下左右四个方向找最高的点
    		int x=u.first+dx[v],y=u.second+dy[v];
    		if(x<1 || x>r || y<1 || y>c || f[x][y]!=-1 || a[x][y]>=a[u.first][u.second])
    			continue;
    		if(a[x][y]>a[t1][t2])
    			t1=x,t2=y;
		}
		if(t1==0 || t2==0)
			continue;
		f[t1][t2]=f[u.first][u.second]+1;
    	ans=max(ans,f[t1][t2]);//求最长
    	q.push(make_pair(t1,t2));
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			cin>>a[i][j];
	a[0][0]=M;
	for(int i=1;i<=r;i++)//从每个点开始搜索
		for(int j=1;j<=c;j++)
			bfs(i,j);
	cout<<ans<<endl;
	return 0;
}
2024/8/16 15:28
加载中...