\(\textbf{基础思路：DFS+记忆化。}\)

题意理解

nbvvnv

基本框架

#include<bits/stdc++.h>
#define For(looper,begin,end) for(int looper=begin;looper<=end;looper++)
using namespace std;

int N,M,x,y,K;
char wt[205][205];
int s[205],t[205],d[205];

int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>N>>M>>x>>y>>K;
	For(i,1,N){
		For(j,1,M){
			wt[i][j]=getchar();
		}
		getchar();
	}
	For(i,1,K){
		cin>>s[i]>>t[i]>>d[i];
	}
	cout<<dfs(1,x,y)<<endl;
	return 0;
}

DFS函数编写

越界考虑

if(time_slice>K){
	return 0;
}

记忆化

else if(rem[time_slice][x][y]!=-1){
	return rem[time_slice][x][y];
}

计算时间长度，更新距离，完成搜索

int time_length = t[time_slice] - s[time_slice] + 1;
int nx = x, ny = y;
for (int i = 1; i <= time_length; i++) {
	nx += X[d[time_slice]];
	ny += Y[d[time_slice]];
	if (nx < 1 || nx > N || ny < 1 || ny > M) {
		break;
	} else if (wt[nx][ny] == 'x') {
		break;
	} else if (1) {
		result = max(result, i + dfs(time_slice + 1, nx, ny));
	}
}

这里有几个点需要注意。

• 一定要注意X与Y坐标的偏移量！
• 判断越界
• x的坐标是不行的哦，我就忘记了。

记忆，返回

rem[time_slice][x][y] = result;
return result;

拼合

#include<bits/stdc++.h>
#define For(looper,begin,end) for(int looper=begin;looper<=end;looper++)
using namespace std;

int N, M, x, y, K;
char wt[205][205];
int s[205], t[205], d[205];
int rem[205][205][205];
const int X[] = {0, -1, 1, 0, 0};
const int Y[] = {0, 0, 0, -1, 1};

int dfs(int time_slice, int x, int y) {
	if (time_slice > K) {
		return 0;
	} else if (rem[time_slice][x][y] != -1) {
		return rem[time_slice][x][y];
	}
	int time_length = t[time_slice] - s[time_slice] + 1;
	int nx = x, ny = y;
	int result = dfs(time_slice + 1, x, y);
	for (int i = 1; i <= time_length; i++) {
		nx += X[d[time_slice]];
		ny += Y[d[time_slice]];
		if (nx < 1 || nx > N || ny < 1 || ny > M) {
			break;
		} else if (wt[nx][ny] == 'x') {
			break;
		} else if (1) {
			result = max(result, i + dfs(time_slice + 1, nx, ny));
		}
	}
	rem[time_slice][x][y] = result;
	return result;
}

int main() {
	memset(rem, -1, sizeof(rem));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> x >> y >> K;
	For(i, 1, N) {
		For(j, 1, M) {
			wt[i][j] = getchar();
		}
		getchar();
	}
	For(i, 1, K) {
		cin >> s[i] >> t[i] >> d[i];
	}
	cout << dfs(1, x, y) << endl;
	return 0;
}

预期得分：\(\color{green}\textbf{100分}\)

实际得分：\(\color{red}\textbf{0分}\)

艰难的debug之旅

我在在线IDE上测试了一下。

最后翻了翻题解，才发现输入可能有问题（具体我也不知道是什么问题）。

For(i,1,N){
	cin>>wt[i]+1;
}

结果是显然的。

最终程序

#include<bits/stdc++.h>
#define For(looper,begin,end) for(int looper=begin;looper<=end;looper++)
using namespace std;

int N, M, x, y, K;
char wt[205][205];
int s[205], t[205], d[205];
int rem[205][205][205];
const int X[5] = {0, -1, 1, 0, 0};
const int Y[5] = {0, 0, 0, -1, 1};

int dfs(int time_slice, int x, int y) {
	if (time_slice > K) {
		return 0;
	} else if (rem[time_slice][x][y] != -1) {
		return rem[time_slice][x][y];
	}
	int time_length = t[time_slice] - s[time_slice] + 1;
	int nx = x, ny = y;
	int result = dfs(time_slice + 1, x, y);
	For(i, 1, time_length) {
		nx += X[d[time_slice]];
		ny += Y[d[time_slice]];
		if (nx < 1 || nx > N || ny < 1 || ny > M) {
			break;
		} else if (wt[nx][ny] == 'x') {
			break;
		} else if (1) {
			result = max(result, i + dfs(time_slice + 1, nx, ny));
		}
	}
	rem[time_slice][x][y] = result;
	return result;
}

int main() {
	memset(rem, -1, sizeof(rem));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> x >> y >> K;
	For(i, 1, N) {
		cin >> wt[i] + 1;
	}
	For(i, 1, K) {
		cin >> s[i] >> t[i] >> d[i];
	}
	cout << dfs(1, x, y) << endl;
	return 0;
}