【官方题解】bfs+预处理

【题目大意】

在一个 $n /times m$ 的棋盘上有一些格子是障碍物，如烟大帝要从 $a_{1,1}$ 走到 $a_{n,m}$ 每次可以选择上下左右四个方向前进一格或者一直前进直到碰到障碍物，这两种方式都消耗1体力求她到达终点的最小消耗体力，如果无法到达输出-1。

Subtask1: 100%

【算法分析】

本题采用bfs（广度优先搜索算法，预处理。

我们只需要上下左右预处理每一个点到达障碍物的位置，建立类似单向边的方式即可，之后进行bfs遍历找到终点的高度输出即可。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,m,h[3003][3003],d[4][2][3003][3003],g[2][4]={{1,0,-1,0},{0,1,0,-1}};

char c[3003][3003];

int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>c[i]+1;
	for (int i=1;i<=n;i++) {
		ll f=0;
		for (int j=1;j<=m;j++){
			if (c[i][j]=='*') d[0][0][i][j]=i,d[0][1][i][j]=(f?d[0][1][i][j-1]:j),f=1;
			else f=0;
		}
		f=0;
		for (int j=m;j;j--){
			if (c[i][j]=='*') d[1][0][i][j]=i,d[1][1][i][j]=(f?d[1][1][i][j+1]:j),f=1;
			else f=0;
		}
	}
	for (int j=1;j<=m;j++){
		ll f=0;
		for (int i=1;i<=n;i++){
			if (c[i][j]=='*') d[2][1][i][j]=j,d[2][0][i][j]=(f?d[2][0][i-1][j]:i),f=1;
			else f=0;
		}
		f=0;
		for (int i=n;i;i--){
			if (c[i][j]=='*') d[3][1][i][j]=j,d[3][0][i][j]=(f?d[3][0][i+1][j]:i),f=1;
			else f=0;
		}
	}
	deque<pair<ll,ll>> q;
	q.push_back({1,1});
	h[1][1]=1;
	while(!q.empty()){
		ll x=q.front().first,y=q.front().second;
		q.pop_front();
		for (int i=0;i<4;i++){
			ll xx=x+g[0][i],yy=y+g[1][i];
			if (xx>=1&&xx<=n&&yy>=1&&yy<=m&&c[xx][yy]=='*'&&!h[xx][yy]){
				h[xx][yy]=h[x][y]+1;
				q.push_back({xx,yy});
			}
			xx=d[i][0][x][y],yy=d[i][1][x][y];
			if (!h[xx][yy]){
				h[xx][yy]=h[x][y]+1;
				q.push_back({xx,yy});
			}
		}
	}
	cout<<h[n][m]-1;
}