#include <iostream>
#include
#include
#include
using namespace std;
const int MAXN = 105;
int n, m, ans, dp[MAXN][MAXN][2];
char mp[MAXN][MAXN];
inline bool check(int x, int y){
if(x>0 && x<=n && y>0 && y<=m && mp[x][y]==‘.‘){
return true;
}else{
return false;
}
}
void fun(){
memset(dp, 0x3f3f3f3f, sizeof(dp));
dp[1][1][0] = dp[1][1][1] = 0;
int obstacle, rt, r, b, lb;
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
obstacle = check(i, j)? 0:1;
rt = check(i-1, j+1)?1:0;
lb = check(i+1, j-1)?1:0;
b = check(i+1, j)?1:0;
r = check(i, j+1)?1:0;
/// right
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0] + obstacle + rt + b );
dp[i][j][0] = min(dp[i][j][0], dp[i][j-1][0] + obstacle );
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][1] + obstacle + b);
dp[i][j][0] = min(dp[i][j][0], dp[i][j-1][1] + obstacle + lb);
// down
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][0] + obstacle + rt );
dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][0] + obstacle + r );
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1] + obstacle );
dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][1] + obstacle + lb + r);
}
}
}
int main(){
freopen("in.txt", "r", stdin);
while(scanf("%d %d", &n, &m) != EOF){
for(int i=1; i<=n; ++i){
getchar();
scanf("%s", mp[i]+1);
}
fun();
ans = min( dp[n][m][0], dp[n][m][1] );
printf("%d\n", ans );
}
return 0;
}
京公网安备 11010802041100号