-
Notifications
You must be signed in to change notification settings - Fork 0
/
MISERMAN.c
49 lines (39 loc) · 968 Bytes
/
MISERMAN.c
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#define INF 9999999
int arr[100][100];
int row, col;
int cache[100][100];
int min(int a, int b, int c, int d) {
if(a<=b && a<=c && a<=d)
return a;
else if(b<=c && b<=a && b<=d)
return b;
else if(c<=b && c<=a && c<=d)
return c;
else
return d;
}
int PSTONE(int x, int y) {
if(x>=row)
return 0;
if(y<0 || y>=col)
return INF;
if(cache[x][y]!=-1)
return cache[x][y];
if(x==0)
return cache[x][y]= min(PSTONE(x, y+1), PSTONE(x+1, y-1) + arr[x][y], PSTONE(x+1, y) + arr[x][y], PSTONE(x+1, y+1) + arr[x][y]);
else
return cache[x][y]= min(INF, PSTONE(x+1, y-1) + arr[x][y], PSTONE(x+1, y) + arr[x][y], PSTONE(x+1, y+1) + arr[x][y]);
}
int main() {
int i, j;
scanf("%d%d", &row,&col);
for(i=0; i<row; i++)
for(j=0; j<col; j++)
cache[i][j]=-1;
for(i=0; i<row; i++)
for(j=0; j<col; j++)
scanf("%d", &arr[i][j]);
printf("%d\n", PSTONE(0,0));
return 0;
}