题目链接

题目描述

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

输入描述

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

输出描述

输出最小代价。

输入样例

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5

输出样例

23

思路

深度优先搜索的思想，递归进行四个方向的搜索，初始设定代价为整型上限INT_MAX，到达终点更新最小代价

代码

#include<bits/stdc++.h>
using namespace std;

int a[6][6];
int x,y,x2,y2;
//上下左右四个方向
int direction[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; 
int mincost=INT_MAX;//最小代价  
int visit[6][6]={0};//是否访问过
 
//深度优先搜索
void dfs(int x,int y,int status,int cost){
    //到达终点
    if(x==x2&&y==y2){
        mincost=min(mincost,cost);
        return;
    }
    
    //当前代价大于了之前的代价，返回
    if(cost>mincost){        
        return;
    }
 
    visit[x][y]=1;//当前节点已经被访问
 
    //向四个方向进行搜索
    for(int i=0;i<4;i++){
    	//更新方向
        int nx=x+direction[i][0];
        int ny=y+direction[i][1];
 
        //新方向在棋盘内，并且没有被访问
        if((nx>=0&&nx<6&&ny>=0&&ny<6)&&(visit[nx][ny]==0)){
            //新的代价
            int nc=a[nx][ny]*status;
            //新的状态
            int ns=(nc%4)+1;
            //从此方向进行搜索
            dfs(nx,ny,ns,nc+cost);
            //失败，清除标记便于下次搜索
            visit[nx][ny]=0;
        }
    }
}

int main(){
    for(int i = 0;i<6;i++){
        for(int j = 0;j<6;j++){
            cin>>a[i][j];
        }        
    }
    cin>>x>>y>>x2>>y2;
    dfs(x,y,1,0);
    cout<<mincost<<endl;
    return 0;
}

Tip

本来变量用的是x1,y1,x2,y2，结果报错说y1已经被定义过了，才发现是math.h里定义了y0,y1,yn,j0,j1,jn