80分代码求助
查看原帖
80分代码求助
750955
bengyy楼主2022/8/26 08:33
//1434 滑雪
#include <bits/stdc++.h>
using namespace std;
int R, C;
int m[110][110], s[110][110], vis[110][110], stotal, depth[1001000];
int mx[4] = {0,1,0,-1}, my[4] = {1,0,-1,0};//right down left up

struct Startpoint {
	int y, x;
}st[10010], q[10010];

void findstart(int x, int y){//actually it is a dfs判断每一个点是否可以成为出发点,只有比周围点都高才可能成为出发点
	if (y == 0 || x == 0 || y == R+1 || x == C+1) {s[y][x] = -1; return;}
	if (vis[y][x] == 1) {return;}
	for (int i = 0; i <= 3; i++) {
		int cmpx = x+mx[i], cmpy = y+my[i];
		if (cmpx >= 1 && cmpy >= 1 && cmpx <= R && cmpy <= C) {
			if (m[cmpy][cmpx] < m[y][x]) {s[cmpy][cmpx] = 1;}//0 means 'is a start'  1 means 'not a start'
			else if (m[cmpy][cmpx] > m[y][x]) {s[y][x] = 1;}
			vis[y][x] = 1;
			findstart(cmpx, cmpy);
		}
	}
}

int main() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> m[j][i];//m[y][x]
		}
	}
	findstart(R/2, C/2);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (s[j][i] == 0) {st[stotal++] = {j,i};}
		}
	}
	int maxlength = 1;
	for (int i = 0; i < stotal; i++) {
		//cout << st[i].x << ' ' << st[i].y << endl;
		int l = 1, r = 1;
		depth[1] = 1;
		q[1] = st[i];
		while (l <= r) {//广度优先搜索 以depth确定步数
			for (int j = 0; j < 4; j++) {
				int fx = q[l].x+mx[j];
				int fy = q[l].y+my[j];
				if (m[fy][fx] < m[q[l].y][q[l].x] && fy >= 1 && fx >= 1 && fy <= C && fx <= R) {
					r++;
					q[r].x = fx, q[r].y = fy;
					depth[r] = depth[l] + 1;
					//cout << q[r].x << ' ' << q[r].y << endl;
				}
			}
			l++;
		}
		maxlength = (maxlength >= depth[r] ? maxlength: depth[r]);
	}
	cout << maxlength;
	return 0;
}

有RE 错误是内存溢出 有一个WA

2022/8/26 08:33
加载中...