1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
int maze[100][100];
int rightSteps[100][100];
int btmSteps[100][100];
int min(int x, int y)
{
    return x < y ? x :y;
}
int main()
{
    int n, m;
    scanf("%d%d",&n, &m);
    char ch = getchar();
    for(int i = 0; i < n; i++ )
    {
        int j = 0;
        while((ch = getchar())!='\n') maze[i][j++] = ch == '.' ? 0 : 1;
    }
    for(int i = 0; i < n; i++ ) rightSteps[i][0] = m + n;
    for(int j = 0; j < m; j++ ) btmSteps[0][j] = m + n;
    rightSteps[0][0] = maze[0][0] ? 1 : 0;
    btmSteps[0][0] = rightSteps[0][0] + ((m == 1 || maze[0][1]) ? 0:1);
    for(int i = 1; i < n; i++ ) btmSteps[i][0] = btmSteps[i-1][0] +  maze[i][0];
    for(int j = 1; j < m; j++ ) rightSteps[0][j] = rightSteps[0][j-1] + maze[0][j];
    for(int i = 1; i < n; i++ )
    {
        for(int j = 1; j < m; j++ )
        {
            int btm2right = btmSteps[i][j-1] + ((i==n-1 || maze[i+1][j-1]) ? 0 : 1);
            rightSteps[i][j] = maze[i][j] + min(btm2right, rightSteps[i][j-1]);
            int right2btm = rightSteps[i-1][j] + (j == m-1 || maze[i-1][j+1] ? 0 : 1);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX