思路：本题考虑用搜索，以起点为树根，dfs遍历所有点，在适当的条件下剪枝。

剪枝条件：当前路径的代价总和sum大于目前已知的到终点的最小代价ans时，即可剪枝

ans更新条件：到达终点且sum更小时，更新ans。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int ans=1e9;//ans暂存当前能到达终点的搜索路径的代价最小值
int map[6][6];//存棋盘
bool visit[6][6];//存储每个位置是否被搜索过
int startx,starty,endx,endy;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//上下左右四个移动方向
void dfs(int x,int y,int sum,int status)//sum暂存当前搜索路径的代价值,status存储上一结点的状态值
{
    if(sum<ans)//剪枝条件：若sum>ans则剪枝
    {
        if(x==endx&&y==endy)//若当前搜索路径走到终点，则更新ans的值
        {
            ans=sum;
            return ;
        }

        for(int i=0;i<4;i++)
        {
            int tempx=x+dir[i][0];
            int tempy=y+dir[i][1];
            if(!visit[tempx][tempy]&&tempx>=0&&tempx<6&&tempy>=0&&tempy<6)
            {
                int cost=status*map[tempx][tempy];
                int sum2=cost+sum;
...