Pro_17022025 Timeout

 avatar
user_1164828
c_cpp
2 months ago
1.4 kB
2
Indexable
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int N, M;
long long map[505][505];
int visited[505][505];
int maxStep;
long long maxScore;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int check(int x, int y) {
	return x >= 0 && x < N && y >= 0 && y < M;
}


void DFS(int row, int col, int val, int step, long long totalScore) {
	if (maxStep < step) {
		maxStep = step;
		maxScore = totalScore;
	}
	if (maxStep == step && maxScore < totalScore) {
		maxScore = totalScore;
	}
	visited[row][col] =  1;
	int x = row;
	int y = col;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (check(nx, ny) && map[nx][ny] > map[x][y] && !visited[nx][ny]) {
			visited[nx][ny] = 1;
			step += 1;
			totalScore += map[nx][ny];
			DFS(nx, ny, map[nx][ny], step, totalScore);
			totalScore -= map[nx][ny];
			step -= 1;
			visited[nx][ny] = 0;
		}
	}
	visited[row][col] = 0;
}

int main() {
	freopen("text.txt", "r", stdin);
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N >> M;
		maxScore = 0;
		maxStep = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> map[i][j];
				visited[i][j] = 0;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				DFS(i, j, map[i][j], 1, map[i][j]);
			}
		}
		cout << "#" << t << " " << maxStep << " " << maxScore << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment