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 <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int inf = 0x7fffffff;
int a[maxn][maxn];
int vis[maxn][maxn];
int ans = inf;
int n;
// 0 down
// 1 right
void dfs(int i,int j,int last, int sum,int cnt)
{
    if(cnt>50)
        return ;
    sum += a[i][j];
    if(last==-1)
        cnt += 1;
    if(sum>=ans)
        return ;
    if(i==n-1 && j==n-1)
    {
        ans = min(ans,sum);
        return ;
    }
    if(i+1<n && !vis[i+1][j])
    {
        vis[i+1][j] = 1;
        if(last==1)
            dfs(i+1, j, 0, sum+cnt,cnt*2);
        else
            dfs(i+1, j, 0, sum,cnt);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX