穿越雷区
X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。
数据格式要求：
输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。
要求输出一个整数，表示坦克从A区到B区的最少移动步数。
如果没有方案，则输出-1
例如：
用户输入：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
则程序应该输出：
10
资源约定：
峰值内存消耗 < 512M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
#include<iostream>
using namespace std;
char map[110][110];
int vis[110][110],n,sum=1000000;
void dfs(int ans,int x,int y){
if(ans>=sum)//sum只取最小的
return;
if(map[x][y]=='B'){//到达终点
sum=ans;
return;
}
vis[x][y]=1;
if((x-1)>=0&&vis[x-1][y]==0&&(map[x][y]!=map[x-1][y]))//四个方向并且相邻两个符号不同
dfs(ans+1,x-1,y);
if((y-1)>=0&&vis[x][y-1]==0&&(map[x][y]!=map[x][y-1]))
dfs(ans+1,x,y-1);
if((x+1)>=0&&vis[x+1][y]==0&&(map[x][y]!=map[x+1][y]))
dfs(ans+1,x+1,y);
if((y+1)>=0&&vis[x][y+1]==0&&(map[x][y]!=map[x][y+1]))
dfs(ans+1,x,y+1);
vis[x][y]=0;
}
int main(){
scanf("%d",&n);
int x,y;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>map[i][j];//输入数据
if(map[i][j]=='A'){//记录起点
x=i;
y=j;
}
}
}
dfs(0,x,y);
if(sum==1000000)//没法走到终点
printf("-1\n");
else
printf("%d\n",sum);
return 0;
}#include<iostream>
#include<cstring>
#include<queue>//我们使用STL中的队列容器
using namespace std;
char map[101][101];
int n;
//以下两个数组为坦克走的四个方向
int bx[4]={-1,1,0,0};
int by[4]={0,0,-1,1};
//定义结构体，方便广搜时入队、出队
struct poi{
int x;//记录该点横坐标
int y;//记录该点纵坐标
int step;//记录从起始点走到该点的步数
};
void bfs(int x,int y){
int vis[101][101]={0};//标记某点是否访问过
queue<poi>path;//定义队列path
int row,col,step_n;//三个中间变量，对应结构体的三个变量
poi p1;//起始点'A'
p1.x=x;//起始点横坐标
p1.y=y;//起始点纵坐标
p1.step=0;//‘A’点的步数肯定是0
path.push(p1);//'A'点入列
vis[x][y]=1;//标记'A'点已访问
while(!path.empty()){//循环遍历，相当于以A为圆心，一圈一圈向四周扩展访问
//以下三行用来访问当前队首元素，依次获取坐标和步数
row=path.front().x;
col=path.front().y;
step_n=path.front().step;
//获取之后，元素出队
path.pop();
for(int i=0;i<4;i++){//向四个方向探索能否走下去
if(row+bx[i]>=n||row+bx[i]<0||col+by[i]>=n||col+by[i]<0)
//如果到达边界
continue;
if(vis[row+bx[i]][col+by[i]]==0){//要求该点必须未访问过才能进行下列操作
if(map[row][col]!=map[row+bx[i]][col+by[i]]){
//当前该点和接下要走到的点不能相等
//满足以上条件，就可以放心大胆的"走"了
//定义p2，通过p1给它赋值，然后入队，就相当于“走”到了下一点了
poi p2;
p2.x=row+bx[i];
p2.y=col+by[i];
p2.step=step_n+1;
path.push(p2);
vis[p2.x][p2.y]=1;
if(map[p2.x][p2.y]=='B'){//判断是否走完
cout<<p2.step<<endl;//走到终点的步数一定是最短的
return;
}
}
}
}
//如果四个方向都走不通，则说明无路可走，输出-1，直接返回
cout<<-1<<endl;
return;
}
}
int main(){
cin>>n;
int i,j;
char a;
for(i=0;i<n;i++){//接收“地图”
for(j=0;j<n;j++){
cin>>a;
if(a==' '){//注意要忽略空格
--j;
continue;
}
else{
map[i][j]=a;
}
}
}
for(i=0;i<n;i++){//用于找到入口'A'，因为A不一定在map[0][0]位置
for(j=0;j<n;j++){
if(map[i][j]=='A'){
bfs(i,j);
break;
}
}
break;
}
return 0;
}
转载自原文链接, 如需删除请联系管理员。
原文链接：蓝桥杯——穿越雷区（搜索），转载请注明来源！