[C++知识库]蓝桥杯2015年第六届C/C++A组国赛第四题-穿越雷区

Idea

求最短路径，用bfs解题
code评测地址

AC Code

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX_SIZE 101
struct node {
	int x,y;
	int step;
};

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

char a[MAX_SIZE][MAX_SIZE];
bool vis[MAX_SIZE][MAX_SIZE];

queue<node> Q;

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
			
	node first;
	first.x=0;
	first.y=0;
	first.step=0;
	Q.push(first);
	vis[0][0]=1;
	int ans = 1000000;
	while(!Q.empty()){
		node cur = Q.front();
		Q.pop();
		int x=cur.x;
		int y=cur.y;
		if(a[x][y]=='B'){
			if(cur.step<ans) ans = cur.step;
			continue;
		}
		for(int i=0;i<4;i++){
			int nx = x+dx[i];
			int ny=y+dy[i];
			if(nx>=0&&nx<n&&ny>=0&&ny<n&&!vis[nx][ny]&&a[x][y]!=a[nx][ny]){
				node curN;
				curN.x=nx;
				curN.y=ny;
				curN.step=cur.step+1;
				Q.push(curN);
				vis[nx][ny]=1;
			}
		}
	} 
	cout<<(ans==1000000?-1:ans);
	return 0;
}