一个小游戏引起的算法思考，大家一起交流一下

事情是这样的，几个月前玩蛋ke机dong队，里面有个活动规则如下：
在一个7*9个小格子组成的长方形的地图里走15步，起始坐标是第5排第4个格子，路径连续且不能有交叉、重复，7*9个小格子每个随机对应0、1、2、5积分。求能拿到最高积分的路径。
当时来了兴趣就写了下计算路径的代码，但效率很低执行出结果需要差不多两分钟，今天偶然有翻出来了，就想看看有没有啥优化空间，求各位大佬指路！！！
其中一个地图按积分转化为二位数组后如下：

我的计算代码如下：
public function dk(){
set_time_limit(0);
$start_time = time();
$map = array(
array(5,1,0,2,0,5,0),
array(0,0,0,0,0,1,0),
array(1,1,1,0,2,0,2),
array(2,1,2,1,1,0,1),
array(0,0,0,0,1,1,2),
array(1,1,2,1,0,0,0),
array(1,1,0,0,1,0,0),
array(5,0,0,1,0,1,1),
array(0,1,1,1,1,0,1)
);
$start_y = 4;
$start_x = 3;
$step = 15;
$get_data = array(
'' => array(
'step' => $step,
'score'=>0,
'have_map' => array(
$start_y.'-'.$start_x
)
)
);
$this->move_path($start_y,$start_x,$map,$get_data,'');
$max = array('score'=>0,'path'=>'');
foreach ($get_data as $k=>$v){
$score = $v['score'];
if($score>$max['score'] ){
$max['score'] = $v['score'];
$max['path'] = $k;
}
}
$end_time = time();
echo '计算数据：'.count($get_data).'条,查找用时：'.($end_time-$start_time).'秒'.PHP_EOL;
echo '最优路径：'.$max['path'].',得分：'.($max['score']*10).PHP_EOL;
}
private function move_path($now_y,$now_x,$map,&$get_data,$now_path){
if($now_x>0){
$new_y = $now_y;
$new_x = $now_x-1;
$next_path = $now_path.'←';
$this->move_path_next($new_y,$new_x,$map,$now_path,$get_data,$next_path);
}
if($now_x<6){
$new_y = $now_y;
$new_x = $now_x+1;
$next_path = $now_path.'→';
$this->move_path_next($new_y,$new_x,$map,$now_path,$get_data,$next_path);
}
if($now_y>0){
$new_y = $now_y-1;
$new_x = $now_x;
$next_path = $now_path.'↑';
$this->move_path_next($new_y,$new_x,$map,$now_path,$get_data,$next_path);
}
if($now_y<8){
$new_y = $now_y+1;
$new_x = $now_x;
$next_path = $now_path.'↓';
$this->move_path_next($new_y,$new_x,$map,$now_path,$get_data,$next_path);
}
}
private function move_path_next($new_y,$new_x,$map,$now_path,&$get_data,$next_path){
$now_data = $get_data[$now_path];
$new_have_map = $new_y.'-'.$new_x;
if($now_data['step']>0){
if(!in_array($new_have_map,$now_data['have_map'])) {
$get_score = $map[$new_y][$new_x];
$all_score = $now_data['score'] + $get_score;
$tmp_have_path = $now_data['have_map'];
$tmp_have_path[] = $new_have_map;
$save_data['step'] = $now_data['step'] - 1;
$save_data['score'] = $all_score;
$save_data['have_map'] = $tmp_have_path;
$get_data[$next_path] = $save_data;
$this->move_path($new_y, $new_x, $map, $get_data, $next_path);
}
}
}