题目描述

    有一个6*6的棋盘，每个棋盘上都有一个数值，现在又一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：     1、只能沿上下左右四个方向移动     2、总代价是没走一步的代价之和     3、每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积     4、初始状态为1     每走一步，状态按如下公式变化：（走这步的代价%4）+1。

输入描述:

    每组数据一开始为6*6的矩阵，矩阵的值为大于等于1小于等于10的值，然后四个整数表示起始坐标和终止坐标。

输出描述:

    输出最小代价。

链接：https://www.nowcoder.com/questionTerminal/368c98c7bff54a30bba29ae1ba017d55
来源：牛客网

#include "stdio.h"
#include "iostream"
#include "limits.h"
#include "string.h"
using namespace std;
 
int chess[6][6];
int min_cost;
int start_a,start_b,end_c,end_d;
 
void func(int a,int b,int cost,int state,int visit[6][6]){
    if(a == end_c && b == end_d)
        min_cost = min(cost,min_cost);
    else{
        if(cost<min_cost){
            if(b-1>=0 && !visit[a][b-1]){
                visit[a][b-1] = 1;
                func(a,b-1,cost+chess[a][b-1]*state,(chess[a][b-1]*state)%4+1,visit);
                visit[a][b-1] = 0;
            }
            if(b+1<6 && !visit[a][b+1]){
                visit[a][b+1] = 1;
                func(a,b+1,cost+chess[a][b+1]*state,(chess[a][b+1]*state)%4+1,visit);
                visit[a][b+1] = 0;
            }
            if(a+1<6 && !visit[a+1][b]){
                visit[a+1][b] = 1;
                func(a+1,b,cost+chess[a+1][b]*state,(chess[a+1][b]*state)%4+1,visit);
                visit[a+1][b] = 0;
            }
            if(a-1>=0 && !visit[a-1][b]){
                visit[a-1][b] = 1;
                func(a-1,b,cost+chess[a-1][b]*state,(chess[a-1][b]*state)%4+1,visit);
                visit[a-1][b] = 0;
            }
        }
    }
}
int main()
{
    for(int i = 0;i<6;i++)
        for (int j = 0;j<6;j++)
            cin>>chess[i][j];
    cin>>start_a>>start_b>>end_c>>end_d;
    min_cost = INT_MAX;
    int visit[6][6];
    memset(visit,0,sizeof(visit));
    func(start_a,start_b,0,1,visit);
    cout<<min_cost<<endl;
    return 0;
}