题解

看到THUNDER的2.2s提交记录有点慌，所以选择了用内存换时间.
没算过THUNDER代码的最坏情况，但感觉是 $O(n^3)$，极限数据会超时.
预处理一直滑，碰到障碍物时停止的坐标，这样就可以把这种情况降至 $O(1)$，总时间复杂度降至 $O(n^2)$.
石山代码见谅

#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.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;//预处理，看上去是O(n^3)，实则还是O(n^2)
				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;
}