C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 4ms, 内存消耗: 520K, 提交时间: 2022-09-17 20:16:01

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
const int N = 55;
const int dx[4]{ 0,0,-1,1 }, dy[4]{ -1,1,0,0 };
char g[N][N];
int n, m, r1, c1, r2, c2;

bool valid(int x, int y)
{
	return x >= 1 && y >= 1 && x <= n && y <= m;
}

struct Node
{
	int r, c, t;
	bool operator < (const Node& o) const
	{
		return t > o.t;
	}
};

priority_queue<Node> q;

int bfs()
{
	q.push({ r1,c1,0 });
	g[r1][c1] = '0';
	while (q.size())
	{
		Node f = q.top();
		q.pop();
		if (f.r == r2 && f.c == c2)
		{
			return f.t;
		}
		for (int i = 0; i <= 3; ++i)
		{
			int rr = f.r + dx[i], cc = f.c + dy[i];
			if (valid(rr, cc) && g[rr][cc] != '#' && g[rr][cc] != '0')
			{
				g[rr][cc] = '0';
				q.push({ rr,cc,f.t + 1 });
			}
			while (valid(rr, cc) && g[rr][cc] == '#')
			{
				rr += dx[i];
				cc += dy[i];
			}
			if (valid(rr, cc) && g[rr][cc] == '.')
			{
				//g[rr][cc] = '0';
				q.push({ rr,cc,f.t + 2 });
			}
		}
	}
	return -1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> g[i][j];
		}
	}
	cin >> r1 >> c1 >> r2 >> c2;
	++r1, ++r2, ++c1, ++c2;
	if (g[r2][c2] == '#')
	{
		cout << -1 << '\n';
		return 0;
	}
	int ans = bfs();
	cout << ans << '\n';
	return 0;
}

C++(clang++11) 解法, 执行用时: 14ms, 内存消耗: 524K, 提交时间: 2021-02-28 15:03:57

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
char G[50][50];
int dp[50][50];
int n,m;
struct node{
	int r,c;
};
void BFS(int r1,int c1,int r2,int c2){
	dp[r1][c1]=0;
	queue<node> Q;
	Q.push((node){r1,c1});
	while(!Q.empty()){
		int r=Q.front().r,c=Q.front().c;
		Q.pop();
		for(int i=0;i<4;i++){
			int x=r+dx[i],y=c+dy[i];
			if(G[x][y]=='.'){
				if(x>=0 && x<n && y>=0 && y<m && dp[r][c]+1<dp[x][y]){
					dp[x][y]=dp[r][c]+1;
					Q.push((node){x,y});
				}
			}else{
				while(x>=0 && x<n && y>=0 && y<m && G[x][y]=='#'){
					x+=dx[i];y+=dy[i];
				}
				if(x>=0 && x<n && y>=0 && y<m && dp[r][c]+2<dp[x][y]){
					dp[x][y]=dp[r][c]+2;
					Q.push((node){x,y});
				}
			}
			
		}
	}
} 
int main(){
	int r1,c1,r2,c2;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>G[i][j];
			dp[i][j]=INF;
		}
	}
	cin>>r1>>c1>>r2>>c2;
	BFS(r1,c1,r2,c2);
	if(dp[r2][c2]>=1e9) cout<<-1<<" ";
	else cout<<dp[r2][c2]<<" ";
	return 0;
}