题解 | #小红的皇后#

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> ch(n);
    for(int i = 0; i < n; i++) {
        cin >> ch[i];
    }
    
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(3, n*m)));
    
    dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 1;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(ch[i][j] == '*') continue;
            for(int k = 0; k < 3; k++) {
                if(i-1 >= 0) {
                    dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][k] + (k != 0));
                }
                if(j-1 >= 0) {
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][k] + (k != 1));
                }
                if(i-1 >= 0 && j-1 >= 0) {
                    dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][k] + (k != 2));
                }
            }
        }
    }
    
    int ans = min({dp[n-1][m-1][0], dp[n-1][m-1][1], dp[n-1][m-1][2]});
    if(ans >= n*m) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] ch = new char[n][m];
        for(int i = 0; i < n; i++) {
            ch[i] = sc.next().toCharArray();
        }
        
        int[][][] dp = new int[n][m][3];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], n*m);
            }
        }
        
        dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 1;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(ch[i][j] == '*') continue;
                for(int k = 0; k < 3; k++) {
                    if(i-1 >= 0) {
                        dp[i][j][0] = Math.min(dp[i][j][0], dp[i-1][j][k] + (k != 0 ? 1 : 0));
                    }
                    if(j-1 >= 0) {
                        dp[i][j][1] = Math.min(dp[i][j][1], dp[i][j-1][k] + (k != 1 ? 1 : 0));
                    }
                    if(i-1 >= 0 && j-1 >= 0) {
                        dp[i][j][2] = Math.min(dp[i][j][2], dp[i-1][j-1][k] + (k != 2 ? 1 : 0));
                    }
                }
            }
        }
        
        int ans = Math.min(Math.min(dp[n-1][m-1][0], dp[n-1][m-1][1]), dp[n-1][m-1][2]);
        System.out.println(ans >= n*m ? -1 : ans);
    }
}

n, m = map(int, input().split())
ch = [input() for _ in range(n)]
dp = [[[n*m]*3 for _ in range(m)] for _ in range(n)]

dp[0][0][0] = 1
dp[0][0][1] = 1
dp[0][0][2] = 1

for i in range(n):
    for j in range(m):
        for k in range(3):
            if ch[i][j] == '*':
                continue
            if(i-1>=0):
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][k]+int(k!=0))
            if(j-1>=0):
                dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][k]+int(k!=1))
            if(i-1>=0 and j-1>=0):
                dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][k]+int(k!=2))

ans = min(dp[n-1][m-1][0], dp[n-1][m-1][1], dp[n-1][m-1][2])

if ans >= n*m:
    print(-1)
else:
    print(ans)