2020 計蒜客藍橋杯B 組模拟賽（三）——突破障礙

小明有一個n*m的二維迷宮，在樣例中給出。其中’#'表示障礙物， 'S’表示起點，‘T’表示終點，’.'表示空地。保證起點和終點都是空地。每次移動可以從目前所在空地移動到相鄰的空地，隻能往上下左右四個方向走。

現在他想知道，從起點到終點最少經過幾個障礙物。

輸入格式

第一行兩個整數 n，m。n，m，意義如題所示 。

接下來 n 行每行 m 個字元，表示整張地圖。

輸出格式

輸出一行一個整數表示最少經過幾個障礙物

用bfs隊列實作，加上了判定條件。

#include <bits/stdc++.h>
#define maxn 305
#define maxm 305
using namespace std;
typedef pair<int,int> pii;
char graph[maxn][maxm];
int num[maxn][maxm]; //用來記錄經過了多少個障礙物
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; //上下左右四個方向
queue<pii> q;
int sx,sy,tx,ty; //sx，sy起點坐标，tx，ty終點坐标
int n,m;
void init(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char c;
			cin>>c;
			if(c=='S'){
				sx=i;
				sy=j;
				c='.';
			}
			if(c=='T'){
				tx=i;
				ty=j;
				c='.';
			}
			graph[i][j]=c;
		}
	}
	memset(num,127,sizeof(num));
}
bool inmap(int x,int y){
	if(x>n-1 || x<0 || y>m-1 || y<0){
		return false;
	}
	else return true;
}

int bfs(){
	int x=-1,y=-1;
	num[sx][sy]=0;
	q.push(make_pair(sx,sy));
	while(!q.empty()){
		x=q.front().first;
		y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dir[i][0];
			int yy=y+dir[i][1];
			if(inmap(xx,yy)){
				if(graph[xx][yy]=='.'){
					if(num[xx][yy]>num[x][y]){
						num[xx][yy]=num[x][y];
						q.push(make_pair(xx,yy));
					}

				}
				if(graph[xx][yy]=='#'){
					if(num[xx][yy]>num[x][y]+1){
						num[xx][yy]=num[x][y]+1;
						q.push(make_pair(xx,yy));
					}	
				}
			}
			
		}
	}
	return num[tx][ty];
}

int main(){
	init();
	cout<<bfs();
}