蓝桥杯2015年第六届真题-穿越雷区

题目

题目链接

题解

BFS模板题。

就在模板题的基础上稍微加了点限制而已。

我用的是pair存的，first表示位置，将二维压缩成一维了；second表示步数； 要求正负交替，我就采用异或的思想进行，判断下一个位置能否作为落脚点即可。

不懂如何实现的二维压缩成一维的同学，评论区问一下，我会回复。

代码

#include
using namespace std;
typedef pair PII;
const int N = 110;

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

int n, Ax, Ay, Bx, By, a[N][N], vis[N][N];
char ch;

queue q;

int main()
{
	cin>>n;
	for(int i = 0;i ch, getchar();
		if(ch == 'A') Ax = i, Ay = j;
		else if(ch == 'B') Bx = i, By = j;
		else if(ch == '-') a[i][j] = 0;
		else if(ch == '+') a[i][j] = 1;
	}
	
	q.push(PII(Ax*n+By, 0));
	vis[Ax][Ay] = 1;
	while(!q.empty()) {
		PII p = q.front();
		q.pop();
		int x = p.first / n, y = p.first % n;
		
		for(int i = 0;i