dfs对三错1剩余都是tle
查看原帖
dfs对三错1剩余都是tle
377449
zjq123victorW楼主2022/5/22 18:38
#include<bits/stdc++.h>
#define N 10002
using namespace std;
int n,mcmp=0,mcos=0,dis[N][N],tryi,tryj;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
char mp;
bool a[N][N],vis[N][N];
void dfs(int i,int j,int cmp,int coos){//i,j,周,面 
	mcmp=max(cmp,mcmp),mcos=max(coos,mcos);
	if(vis[i][j]==1||a[i][j]==0)return;
	for(int k=0;k<=3;k++){
		tryi=i+dx[k],tryj=j+dy[k];
		if(tryi<=n&&tryj<=n&&tryi>=1&&tryj>=1){
			vis[i][j]=1;
			dfs(tryi,tryj,cmp+dis[i][j],coos+1);
			vis[i][j]=0;
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){//输入 
		for(int j=1;j<=n;j++){
			cin>>mp;
			a[i][j]=mp=='#'?1:0;
		}
	}
	for(int i=1;i<=n;i++){//计算每一块的周长 
		for(int j=1;j<=n;j++){
			if(a[i][j]==1){
				if(!a[i+1][j])dis[i][j]++;
				if(!a[i][j+1])dis[i][j]++;
				if(!a[i-1][j])dis[i][j]++;
				if(!a[i][j-1])dis[i][j]++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]) dfs(i,j,0,0);
		}
	}
	printf("%d %d",mcos,mcmp);
 	return 0;
}


求大佬指点qwq

2022/5/22 18:38
加载中...