自己写的sb解法
查看原帖
自己写的sb解法
613228
sinnoaa楼主2024/1/18 17:27

帮我算算时间复杂度

#include<bits/stdc++.h>
using namespace std;
const int N = 10;

int g[N][N];
int n, m;
vector<vector<int>> st(N,vector<int>(N));
int backup[N][N];

int fx[8][2] = {1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,-1,-1,1};

int dfs(int x,int y, vector<vector<int>> p){
	int ans = g[x][y];
	for(int i = 0; i < 8; i ++){
		int a = fx[i][0] + x;
		int b = fx[i][1] + y;
		if(a < 1 || b < 1 || a > n || b > m )  continue;
		p[a][b] = 1;	
	}
	p[x][y] = 1;
	int p1 = 0;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(!p[i][j]){
				p1 = max(p1, dfs(i, j, p));
			}
		}
	}
	return ans + p1;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		memset(g,0,sizeof g);
		memset(backup, 0, sizeof backup);
		cin >> n >> m;
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j ++){
				cin >> g[i][j];
			}
		}
		
		int ans = 0;
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j <= m; j ++){
				ans =  max(dfs(i, j, st), ans);
			}
		}
		cout << ans  << endl;
		
		
		
		
		
		
		
	}
}
2024/1/18 17:27
加载中...