题解 | 小红的皇后

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,INF=0x3f3f3f3f;

int n,m;
char g[N][N];
int dp[N][N][3]; 

void solve(){
	
	if(n==1&&m==1){
		cout<<0<<endl;
		return;
	}
	
	memset(dp,0x3f,sizeof(dp));
	
	if(g[1][1]=='.'){
		dp[1][1][0]=1;
		dp[1][1][1]=1;
		dp[1][1][2]=1;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1) continue;
			if(g[i][j]=='*') continue;
			
			if(i-1>=1&&g[i-1][j]=='.'){
				int value=min(dp[i-1][j][0],min(dp[i-1][j][1],dp[i-1][j][2])+1);
				dp[i][j][0]=min(dp[i][j][0],value);
			}
			if(j-1>=1&&g[i][j-1]=='.'){
				int value=min(dp[i][j-1][1],min(dp[i][j-1][0],dp[i][j-1][2])+1);
				dp[i][j][1]=min(dp[i][j][1],value);
			}
			if(i-1>=1&&j-1>=1&&g[i-1][j-1]=='.'){
				int value=min(dp[i-1][j-1][2],min(dp[i-1][j-1][0],dp[i-1][j-1][1])+1);
				dp[i][j][2]=min(dp[i][j][2],value);
			}
		}
	}
	
	int res=INF;
	for(int i=0;i<3;i++){
		res=min(res,dp[n][m][i]);
	}
	
	if(res==INF){
		cout<<-1<<endl;
	}else{
		cout<<res<<endl;
	}
	
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
		}
	}
	
	solve();

    return 0;
}