题解

#include<bits/stdc++.h>
using namespace std;struct node{int x, y, step;};
char a[3005][3005];int dirs[4][3005][3005];bool vis[3005][3005];int dir[4][2]={-1,0,0,-1,0,1,1,0};int n,m;
int bfs(){
	queue<node>q;
	vis[1][1]=1;
	q.push({1,1,0});
	while(!q.empty()){
		node head=q.front();
		q.pop();
		if(head.x==n&&head.y==m)return head.step;
		for(int i=0;i<4;i++){
			int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == '*' && !vis[xx][yy]){
				vis[xx][yy] = 1;
				q.push({xx, yy, head.step + 1});
			}
			if(i < 2){
				xx = head.x, yy = dirs[i][xx][head.y];
				if(!vis[xx][yy]){
					vis[xx][yy] = 1;
					q.push({xx, yy, head.step + 1});
				}
			}else{
				yy = head.y, xx = dirs[i][head.x][yy];
				if(!vis[xx][yy]){
					vis[xx][yy] = 1;
					q.push({xx, yy, head.step + 1});
				}
			}
		}
	}
	return -1;
}
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i] + 1;
	}
	for(int i = 1; i <= n; i++){
		int left = -1;
		for(int j = 1; j <= m; j++){
			if(left == -1 && a[i][j] == '*') left = j;
			else if(left != -1 && a[i][j] == '#'){
				for(int k = left; k < j; k++) dirs[0][i][k] = left, dirs[1][i][k] = j - 1;
				left = -1;
			}
		}
		if(left != -1){
			for(int j = left; j <= m; j++) dirs[0][i][j] = left, dirs[1][i][j] = m;
		}
	}
	for(int i = 1; i <= m; i++){
		int up = -1;
		for(int j = 1; j <= n; j++){
			if(up == -1 && a[j][i] == '*') up = j;
			else if(up != -1 && a[j][i] == '#'){
				for(int k = up; k < j; k++) dirs[2][k][i] = up, dirs[3][k][i] = j - 1;
				up = -1;
			}
		}
		if(up!=-1){for(int j = up; j <= n; j++) dirs[2][j][i] = up, dirs[3][j][i] = n;}
	}cout<<bfs();return 0;}