典型而朴素的记忆化搜索
/***************************************** **文件名：百炼-1088 **Copyright (c) 2010-2020 OrdinaryCrazy **创建人：OrdinaryCrazy **日期：20170806 **描述：百炼1088参考答案 **版本：1.0 ******************************************/ #include <stdio.h> #include <stdlib.h> int place[100][102],r,c,max; int way[102][102]; int maxf(int a,int b) { return a > b ? a : b; } /******************************************* **函数名： **输入：i-需要计算位置的纵坐标，j-需要计算位置的横坐标 **输出：该位置的最大下滑距离 **功能：计算位置(i,j)的最大下滑距离 **作者：OrdinaryCrazy **日期：20170806 **版本：1.0 ********************************************/ int search(int i,int j) { if(way[i][j] || i == 0 || i == r + 1 || j == 0 || j == c + 1) return way[i][j]; int a,b,c,d; a = b = c = d = 0; place[i][j] > place[i-1][j] ? a = search(i-1,j) : 0; place[i][j] > place[i+1][j] ? b = search(i+1,j) : 0; place[i][j] > place[i][j-1] ? c = search(i,j-1) : 0; place[i][j] > place[i][j+1] ? d = search(i,j+1) : 0; return way[i][j] = 1 + maxf(maxf(a,b),maxf(c,d)); } int main() { int i,j; scanf("%d%d",&r,&c); for(i = 1;i <= r;i++) for(j = 1;j <= c;j++) scanf("%d",&place[i][j]); for(i = 1;i <= r;i++) for(j = 1;j <= c;j++) { int tmp = search(i,j); tmp > max ? max = tmp : 0; } printf("%d",max); return 0; }
