(DFS)

JAVA 代码

//DFS + 动态优化
import java.io.*;

public class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int a[][] = new int[6][6],sX,sY,eX,eY,min = (int)1e8,dx[],dy[];
    static boolean mark[][] = new boolean[6][6];
    public static void main(String[] args) throws IOException{
        //分量
        dx = new int[]{0,0,-1,1};//上下左右
        dy = new int[]{-1,1,0,0};
        for(int x = 0; x < 6; x ++){
            for(int y = 0; y < 6; y ++){
                a[x][y] = next();
            }
        }
        sX = next();
        sY = next();
        eX = next();
        eY = next();
        dfs(sX,sY,0,1);
        System.out.println(min);
    }
    static void dfs(int x,int y,int dept,int state){
        if(x == eX && y == eY){
            min = Math.min(min,dept);
        }
        //动态优化,如果这步已经大于当前最小值那么就不继续走
        if(dept > min) {
            return;
        }
        for(int i = 0; i < 4; i ++){
            int X = x + dx[i];
            int Y = y + dy[i];
            if(X < 0 || X > 5 || Y < 0 || Y > 5){
                continue;
            }
            if(!mark[X][Y]){
                int addDept = a[X][Y] * state;
                mark[X][Y] = true;
                dfs(X,Y,(dept + addDept),((addDept % 4) + 1));
                mark[X][Y] = false;
            }
        }

    }
    static int next() throws IOException{
        in.nextToken();
        return (int)in.nval;
    }
}