蓝桥杯2015年第六届真题-穿越雷区-题解（C++代码）

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
char a[100][100];
int n,vis[100][100];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} }; //下右上左
int bx, by,step=99999;
bool check(int i, int j,char c)
{
	if (i >= 0 && i < n && j >= 0 && j < n && vis[i][j] == 0)
	{
		if (c == 'A') return true;
		else return (c != a[i][j]);
	}
	else return false;
}
void dfs(int x,int y,int s)
{
	if (a[x][y]=='B')
	{
		if (s < step)
		{
			step = s;
		}
		return;
	}
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		int dx = x + dir[i][0];
		int dy = y + dir[i][1];
		if (check(dx, dy, a[x][y]))
		{
			dfs(dx, dy, s+ 1);
		}
	}
	vis[x][y] = 0;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 'A')
			{
				bx = i;
				by = j;
			}
		}
	}
	dfs(bx, by,0);
	if (step != 9999)cout << step;
	else cout << "-1";
}