题目 代码

#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
#define heap priority_queue
using namespace std;
typedef long long ll;
inline ll read() {
	char c = getchar();
	ll x = 0, y = 1;
	while(c < 48 || c > 57) y = c == 45 ? -1 : 1, c = getchar();
	while(c >= 48 && c <= 57) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return x * y;
}

const int N = 110;
const int INF = 0x3f3f3f3f;

struct Node {
	int x, y, d;
};

char mapc[N][N];
bool vis[N][N][N];
int cost[N][N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n, m, d, ans;

void bfs() {
	memset(cost, 0x3f, sizeof(cost));
	deque<Node> q;
	q.push_back((Node) {
		1, 1, d
	});
	cost[1][1][d] = 0;
	while(!q.empty()) {
		Node p = q.front();
		q.pop_front();
		if(vis[p.x][p.y][p.d]) continue;
		vis[p.x][p.y][p.d] = 1; 
		for(int i = 0; i < 4; i++) {
			int xx = p.x + dx[i], yy = p.y + dy[i];
			if(xx < 1 || yy < 1 || xx > n || yy > m) continue;
			if(mapc[xx][yy] == 'L') continue;
			if(cost[xx][yy][p.d] > cost[p.x][p.y][p.d] + 1) {
				cost[xx][yy][p.d] = cost[p.x][p.y][p.d] + 1;
				q.push_back(Node {xx, yy, p.d});
			}
			for(int j = 2; j <= p.d; j++) {
				xx += dx[i], yy += dy[i];
				if(xx < 1 || yy < 1 || xx > n || yy > m) break;
				if(mapc[xx][yy] == 'L') continue;
				if(cost[xx][yy][p.d - j] > cost[p.x][p.y][p.d] + 1) {
					cost[xx][yy][p.d - j] = cost[p.x][p.y][p.d] + 1;
					q.push_back(Node {xx, yy, p.d - j});
				}
			}
		}
	}
}

int main() {
	n = read(), m = read(), d = read();
	for(int i = 1; i <= n; i++) {
		scanf("%s", &mapc[i][1]);
	}
	bfs();
	ans = INF;
	for(int i = 0; i <= d; i++) {
		ans = min(ans, cost[n][m][i]);
	}
	if(ans > INF - 100) printf("impossible");
	else printf("%d", ans);
	return 0;
}

结果