Comment

Misaka19017: 2025-12-30 16:59:03

不要用java，java因为编译的缘故，必定会超时

RockyChen0205: 2023-10-31 15:34:49

#include<iostream>
#include<vector>
#include<utility>
#include<cstring>
#include<queue>
using namespace std;
pair<int,int> coordinate0;   //起点
pair<int,int> coordinate1;   //终点
char map[100][100];   //地图
int vis[100][100];     //记录地图上的点到起点的步数
int cors[4]={0,0,-1,1};
int stra[4]={1,-1,0,0};
int w,h;

int bfs(){
	queue<pair<int,int>> q;
        // 把起点推入队列中
	pair<int,int> t={coordinate0.first,coordinate0.second};
	q.push(t);
	while(!q.empty()){
		auto pp=q.front();
		q.pop();
               //所有方向都试一遍
		for(int i=0;i<4;i++){
			int x=pp.first+cors[i];
			int y=pp.second+stra[i];
			if(x>=0 && x<h && y>=0 && y<w && map[x][y]!='#'&&
				vis[x][y]==-1 ){
				vis[x][y]=vis[pp.first][pp.second]+1;
				q.push({x,y});
			}
		}
	}
	return vis[coordinate1.first][coordinate1.second];
}
int main(){
	int T;
	cin>>T;
	vector<int> result;
	for(int i=0;i<T;i++){
		cin>>h>>w;
		for(int x=0;x<h;x++){
			for(int y=0;y<w;y++){
				cin>>map[x][y];
				if(map[x][y]=='S') {
					coordinate0.first=x;
					coordinate0.second=y;
				}
				else if(map[x][y]=='G'){
					coordinate1.first=x;
					coordinate1.second=y;
				}
			}
		}
		memset(vis,-1,sizeof(vis));
		vis[coordinate0.first][coordinate0.second]=0;
		result.push_back(bfs());
	}
	for(int i=0;i<result.size();i++){
		cout<<result[i]<<endl;
	}
}