蓝桥杯2018年第九届真题

真题"/>

蓝桥杯2018年第九届真题

题目

题目链接

题解

BFS。

主要的特殊点在于加了很多特殊的情况，逐一判断即可。

注意vis/st标记数组是三维的第一维是行号，第二维是列号，第三维是能量值，表示是否以该能量值到达过该点。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;int n, k, st[N*N][15];
string a[N];
int dir[2][4] = {-1, 1, 0, 0, 0, 0, -1, 1};struct node {int first, second, third; // first：位置，second：能量值，third：步数 
};int bfs () {queue <node> q;st[0][0] = 1;q.push ({0, 0, 0});while (q.size()) {node t = q.front ();int x = t.first / n; // xint y = t.first % n; // yint m = t.second; // 处于(x,y)位置的能量 int d = t.third; // 到达(x,y)的步数 q.pop ();if (x == n-1 && y == n-1) return d; // 终点 for (int i = 0;i < 4;i ++) {int tx = x + dir[0][i], ty = y + dir[1][i];if (tx < 0 || ty < 0 || tx >= n || ty >= n || a[tx][ty] == '#') continue;int tnext = tx*n+ty; // 下一个位置 if (a[tx][ty] == '%') { // 如果是能量石 if (!st[tnext][k]) st[tnext][k] = 1, q.push ({tnext, k, d+1}); // 如果吃过能量石就不能进入这个if if (!st[tnext][max (0, m-1)]) st[tnext][max (0, m-1)] = 1, q.push ({tnext, max (0, m-1), d+1}); // 如果以m-1的能量值到达过tnext位置，则不会重复 } else if (a[tx][ty] == 'X') { // 如果是陷阱 if (m && !st[tnext][max (0, m-1)]) st[tnext][max (0, m-1)] = 1, q.push ({tnext, max (0, m-1), d+1}); // 只有有能量才能走 } else { // 道路，只要没以m-1的能量到达过就能走 if (!st[tnext][max (0, m-1)]) st[tnext][max (0, m-1)] = 1, q.push ({tnext, max (0, m-1), d+1});}}}return -1;
}int main()
{cin >> n >> k;for (int i = 0;i < n;i ++)cin >> a[i];cout << bfs ();	return 0;
}