棋盘游戏

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
int matrix[10][10];
int x_1,y_1,x_2,y_2;
bool visit[10][10];
int ans ;
int a[] = {-1,1,0,0};
int b[] = {0,0,1,-1};
 
void dfs(int x,int y,int now, int status)
{
    if(x == x_2 && y == y_2)
    {
        ans = min(ans,now);
        return;
    }
    if(now > ans)
    return;
    visit[x][y] = 1;
    
    for(int i = 0 ;i<4;i++)
    {
        int xx = x + a[i],yy = y + b[i];
        if(xx < 0 || xx > 5 || yy < 0 || yy > 5 || visit[xx][yy] == 1)
        continue;
        int cost = matrix[xx][yy] * status;
        int new_status = (cost % 4) + 1;
        dfs(xx,yy,now + cost, new_status);
    }
    visit[x][y] = 0;
}
int main()
{
    while(cin >> matrix[0][0])
    {
        for(int i = 1;i<=5;i++)
        cin >> matrix[0][i];
        memset(visit,0,sizeof(visit));        
        for(int i = 1;i<=5;i++)
        {
            for(int j = 0 ;j<=5;j++)
            {
                cin >> matrix[i][j];        
            }
        }
        ans = 0x3f3f3f3f;
        cin >> x_1 >> y_1 >> x_2 >> y_2 ;
        dfs(x_1,y_1,0,1);
        cout << ans << endl;
    }    
}

//Dijkstra
//复杂度O(n^4)
//比二维的棋子多一维状态

#include <stdio.h>

int detax[] = {1,-1,0,0};
int detay[] = {0,0,1,-1};
const int N = 6;
const int MAXP = 100000;
int matrix[N][N];
int price[N][N][4];
int flag[N][N][4];

void dij() {
    for (int i = 0; i < 4 * N * N; i++){
        int ux = -1;
        int uy = -1;
        int uk = -1;
        int priceMin = MAXP;
        for(int jx = 0; jx < N; jx++) 
            for(int jy = 0; jy < N; jy++) 
                for(int jk = 0; jk < 4; jk++)
                    if(flag[jx][jy][jk] == false && price[jx][jy][jk] < priceMin) {
                        ux = jx;
                        uy = jy;
                        uk = jk;
                        priceMin = price[jx][jy][jk];
                    }
        if(ux == -1)    return;
        flag[ux][uy][uk] = true;
        for(int j = 0; j < 4; j++) {
            int vx = ux + detax[j];
            int vy = uy + detay[j];
            if(vx < 0 || vy < 0 || vx >= N || vy >= N)    continue;
            int pr = (uk+1) * matrix[vx][vy];
            int vk = pr % 4;
            if(flag[vx][vy][vk] == true)    continue;
            if(price[vx][vy][vk] < price[ux][uy][uk] + pr)    continue;
            price[vx][vy][vk] = price[ux][uy][uk] + pr;
        }
    }
}

int main() {
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++) {
            scanf("%d",&matrix[i][j]);
            for(int k = 0; k < 4; k++)
                price[i][j][k] = MAXP;
        }
    int sx,sy,ex,ey;
    scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    price[sx][sy][0] = 0;
    dij();
    int ans = MAXP;
    for(int k = 0; k < 4; k++)
        if(price[ex][ey][k] < ans)
            ans = price[ex][ey][k];
    printf("%d",ans);
}

#include <cstdio>

const int mapSize = 6;
int map[mapSize + 1][mapSize + 1];
bool visited[mapSize + 1][mapSize + 1];
int a, b, c, d;
int ans = 0x3f3f3f3f;
int dir_x[] = {-1, 0, 1, 0};
int dir_y[] = {0, -1, 0, 1};

int min(const int &a, const int &b) {
    return a < b ? a : b;
}

void dfs(const int &x, const int &y,
        const int &curCost, const int &curStatus) {
    if (x == c + 1 && y == d + 1) {
        ans = min(ans, curCost);
        return;
    }
    if (curCost > ans) {
        return;
    }
    //printf("%d, %d\t%d\n", x, y, map[x][y]);
    visited[x][y] = 1;
    for (int i = 0; i < 4; ++i) {
        int next_x = x + dir_x[i];
        int next_y = y + dir_y[i];
        if(next_x < 1 || next_x > 6 || next_y < 1 || next_y > 6 
           || visited[next_x][next_y] == 1) {
            continue;
        }
        int cost = map[next_x][next_y] * curStatus;
        int newStatus = (cost % 4) + 1;
        dfs(next_x, next_y, curCost + cost, newStatus);
    }
    visited[x][y] = 0;
}

int main() {
    for (int i = 1; i <= mapSize; ++i) {
        for (int j = 1; j <= mapSize; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
    scanf("%d%d%d%d", &a, &b, &c, &d);
    dfs(a + 1, b + 1, 0, 1);
    printf("%d\n", ans);
    return 0;
}

	#include <iostream>



	





	





	using namespace std;



	





	int map[8][8];



	bool visited[8][8];



	int res = 0x3f3f3f3f;



	//right left up down



	int dir[4][2] = {{ 1, 0},



	                 {-1, 0},



	                 { 0, -1},



	                 { 0, 1}};



	int s_x, s_y, t_x, t_y;



	





	 /*



	规则：



	 总代价是没走一步的代价之和



	 每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积



	 初始状态为1     每走一步，状态按如下公式变化：（走这步的代价%4）+1。



	 */



	





	void dfs(int x, int y, int val, int state){



	    



	    //搜索结束



	    if (x == t_x && y == t_y){



	        if (val <= res) res = val;



	        //cout<<'hhh';



	        return;



	    }



	    //剪枝



	    if (val >= res){



	        return;



	    }



	    //记当前节点已访问过



	    visited[x][y] = true;



	    for (int i=0; i<4; i++){



	        int new_x = x + dir[i][0];



	        int new_y = y + dir[i][1];



	        //cout<<new_x<<' '<<new_y<<endl;



	        // 下一个节点可以走 && 未访问过



	        if (map[new_x][new_y] != 0 && !visited[new_x][new_y]){



	            visited[new_x][new_y] = true;



	            int cur_val = map[new_x][new_y] * state;



	            dfs(new_x, new_y, val+cur_val, cur_val%4+1);



	            visited[new_x][new_y] = false;



	        }



	    }



	}



	





	int main(){



	    //8*8棋盘 保证最外围的一层都是0



	    for (int i=1; i<=6; i++){



	        for (int j=1; j<=6; j++){



	            cin >> map[i][j];



	        }



	    }



	    cin >> s_x >> s_y >> t_x >> t_y;



	    



	    s_x++;



	    s_y++;



	    t_x++;



	    t_y++;



	    



	    visited[s_x][s_y] = true;



	    dfs(s_x, s_y, 0, 1);



	    cout<<res;



	    



	    



	}

import java.util.Scanner;

public class ChessboardGame {
	private static int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1}};//分别为上下左右四个方向
	private static int minCost;//记录最小代价
	public static void dfs(int[][] map, boolean[][] visited, int sum, int status, int startX, int startY, int endX, int endY) {
		if(sum < minCost) {//剪枝， 如果代价sum大于目前最小代价则不必要继续搜索
			if(startX == endX && startY == endY) {//到终点，更新值
				minCost = sum;
			} else {
				for(int i = 0; i < 4; i++) {
					int tempX = startX + dir[i][0];//更新x值
					int tempY = startY + dir[i][1];//更新y值
					
					//合法性判断
					if(tempX >= 0 && tempX < 6 && tempY >= 0 && tempY < 6 && !visited[tempX][tempY]) {
						//代价计算
						int cost = map[tempX][tempY] * status;
						//表示此坐标已访问
						visited[tempX][tempY] = true;
						//sum = sum + cos, status = cost % 4 + 1
						dfs(map, visited, sum + cost, cost % 4 + 1, tempX, tempY, endX, endY);
						//设为未访问进行递归
						visited[tempX][tempY] = false;
					}
				}
			}
		}
	
	}
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()) {
			int n = cin.nextInt();
			for(int k = 0; k < n; k++) {
				int[][] map = new int[6][6];
				for(int i = 0; i < 6; i++) {
					for(int j = 0; j < 6; j++) {
						map[i][j] = cin.nextInt();
					}
				}
				int startX = cin.nextInt();
				int startY = cin.nextInt();
				int endX = cin.nextInt();
				int endY = cin.nextInt();
				
				boolean[][] visited = new boolean[6][6];
				minCost = Integer.MAX_VALUE;
				//初始时，起始点设为true
				visited[startX][startY] = true;
				dfs(map, visited, 0, 1, startX, startY, endX, endY);
				System.out.println(minCost);
			}
			
		}
		cin.close();
	}

}

#include <iostream>
using namespace std;
int total = 0x7fffffff;
int X, Y; // 终点
#define N 6
int p[N][N]; // 棋盘
bool flag[N][N];
int pos[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
void DFS(int s, int c, int x, int y)// 状态s, 代价c, 从<x,y>起
{
    if (flag[x][y]) return;
    if (c > total) return;// 这个剪枝剪得漂亮

    if (x==X && y==Y) {
        if (total == -1) total = c;
        else total = total<c?total:c;
        return;
    }
    if (x < 0 || y < 0 || x >= N || y >= N) return;

    flag[x][y] = true;// 从<x,y>出发，往下深搜不再允许使用<x,y>这个点
    for (int i = 0; i < 4; i ++) {
        int xx = x+pos[i][0], yy = y+pos[i][1];
        int cc = s * p[xx][yy];
        DFS(cc%4+1,c+cc,xx,yy);
    }
    flag[x][y] = false;// 向上层回溯，故而<x,y>还有可能被用到

    return;
}
int main(void)
{

    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            cin >> p[i][j];
    int x,y;
    cin >> x >> y >> X >> Y;

    DFS(1,0,x,y);

    cout << total << endl;
    return 0;
}

#include<bits/stdc++.h>//动态规划解法
using namespace std;
int a[6][6];
int sign(int a,int b){
    if (a>b)return -1;
    else if(a<b)return 1;
    else return 0;
}
int opt(int x1,int y1,int x2,int y2,int stat){
    int p1,p2,stat1,stat2;
    int sig1=sign(x1,x2),sig2=sign(y1,y2);
    p1=stat*a[x1+sig1][y1];stat1=p1%4+1;
    p2=stat*a[x1][y1+sig2];stat2=p2%4+1;
    if(sig1==0&&sig2==0)return 0;
    if(sig1!=0&&sig2!=0){        
        return min(p1+opt(x1+sig1,y1,x2,y2,stat1),p2+opt(x1,y1+sig2,x2,y2,stat2));
    }
    if(sig1==0) return p2+opt(x1,y1+sig2,x2,y2,stat2);
    else return p1+opt(x1+sig1,y1,x2,y2,stat1);
    
}
int main(){
    int a1,b,c,d;
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
        cin>>a[i][j];
        }
    }
    cin>>a1>>b>>c>>d;
    cout<<opt(a1,b,c,d,1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
//搜索的上下左右四个方向
int direction[4][2]={
    {
        0,1
    },//向左
    {
        0,-1
    },//向右
    {
        1,0
    },//向下
    {
        -1,0
    }//向上
};

int bx,by;//搜索的起点
int ex,ey;//搜索的终点

int bestcost=INT_MAX;//最小代价

int matrix[6][6]={0};//棋盘

int hadvisit[6][6]={0};//标记是否访问

//通过深度搜索寻找最小代价
void dfs(int x,int y,int status,int cost)
{
    //(x,y)是当前访问节点
    //status是题目中规定的状态
    //cost是当前代价
    if(x==ex&&y==ey)
    {
        //已经到达了终点
        bestcost=min(bestcost,cost);
        //最小代价是当前代价和以前总代价的最小值

    }

    if(cost>bestcost)
    {
        //搜索当中当前代价已经大于了以前的代价值
        //返回，不用继续搜索
        return ;
    }

    hadvisit[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)&&(hadvisit[nx][ny]==0))
        {
            //新的代价
            int nc=matrix[nx][ny]*status;
            //新的状态
            int ns=(nc%4)+1;
            //进行搜索试探
            hadvisit[nx][ny]=1;
            dfs(nx,ny,ns,nc+cost);
            //试探失败，清除标记便于下次试探
            hadvisit[nx][ny]=0;
        }
        else
        //继续寻找方向
        continue;
    }
}

int main()
{
    for(int i=0;i<6;i++)
    {
        for(int j=0;j<6;j++)
        {
            scanf("%d",&matrix[i][j]);
        }
    }
    scanf("%d%d%d%d",&bx,&by,&ex,&ey);
    dfs(bx,by,1,0);
    printf("%d\n",bestcost);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <limits.h>
#include<float.h>

using namespace std;
typedef long long LL;

int a[7][7];
int c,d;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool s[7][7];
int res=INT32_MAX;

void dfs(int x,int y,int last,int st)
{
    if(x==c&&y==d) 
    {
        res=min(res,last);
    }
    if(last>=res) return;

    for(int i=0;i<4;i++)
    {
        int x1=x+dir[i][0],y1=y+dir[i][1];
        if(x1>=0&&x1<6&&y1>=0&&y1<6&&!s[x1][y1])
        {
            s[x1][y1]=true;
            dfs(x1,y1,last+st*a[x1][y1],st*a[x1][y1]%4+1);
            s[x1][y1]=false;
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
            cin>>a[i][j];
    
    int a,b;
    cin>>a>>b>>c>>d;
    dfs(a,b,0,1);
    cout<<res<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int a[10][10];
int p[10][10];
int x1, x2, y1, y2;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int search(int x, int y, int state)
{
	if (x == x2 && y == y2)
	{
		p[x][y] = 0;
		return 0;
	}
	if (p[x][y] != -1) return p[x][y];
	
	int &ans = p[x][y];
	ans = 0x3f3f3f3f;
	for (int i = 0; i < 4; i ++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (nx >= 0 && nx < 6 && ny >= 0 && ny < 6)
		{
			int price = state * a[nx][ny];
			ans = min(ans, price + search(nx, ny, (price % 4) + 1));
		}
	}
	return ans;
}

int main()
{
	memset(p, -1, sizeof p);
	for (int i = 0; i < 6; i ++)
	{
		for (int j = 0; j < 6; j ++)
			cin >> a[i][j];
	}

	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	
	int res = search(x1, y1, 1);
	
	printf("%d\n", res);
	
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

int matrix[6][6];
bool visited[6][6];
int pos[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<int> v;

void dfs(int x1, int y1, int x2, int y2, int statue, int cost){
    if(x1 == x2 && y1 == y2) v.push_back(cost);
    else{
        for(int i = 0; i < 4; i++){
            int nx = x1 + pos[i][0];
            int ny = y1 + pos[i][1];
            if(nx < 0 || nx >= 6 || ny < 0 || ny >= 6 || visited[nx][ny]) continue;
            int c = matrix[nx][ny] * statue;
            int s = c % 4 + 1;
            visited[nx][ny] = true;
            dfs(nx, ny, x2, y2, s, cost + c);
            visited[nx][ny] = false;
        }
    }
}

int main(){
    while(scanf("%d", &matrix[0][0]) != EOF){
        for(int i = 0; i < 6; i++){
            for(int j = 0; j < 6; j++){
                if(i == 0 && j == 0) continue;
                else scanf("%d", &matrix[i][j]);
            }
        }
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        memset(visited, false, sizeof(visited));
        visited[x1][y1] = true;
        dfs(x1, y1, x2, y2, 1, 0);
        sort(v.begin(), v.end());
        printf("%d\n", v[0]);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int panel[10][10];
int mincost = INT_MAX;
int a, b, c, d;
int dirx[4] = {0, 1, 0, -1};
int diry[4] = {1, 0, -1, 0};
bool flag[10][10];

void dfs(int x, int y, int cursta, int curcost) {
    if (x == c && y == d) {
        mincost = min(mincost, curcost);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + dirx[i];
        int ty = y + diry[i];
        if (tx >= 0 && tx < 6 && ty >= 0 && ty < 6 && flag[tx][ty] == false) {
            int cost = panel[tx][ty] * cursta;
            int state = cost % 4 + 1;
            if (curcost + cost < mincost) {
                flag[tx][ty] = true;
                dfs(tx, ty, state, curcost + cost);   
                flag[tx][ty] = false;
            }
        }
    }
}

int main() {    
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> panel[i][j];
        }
    }   
    cin >> a >> b >> c >> d;
    flag[a][b] = true;
    dfs(a, b, 1, 0);
    cout << mincost << endl;

    return 0;
}

动态规划+深度搜索

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int INF = 1 << 30;
// 纯动态规划解
int dp[6][6][5];
int a[6][6];
void initial()
{
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
            for (int k = 1; k <= 4; k++)
                dp[i][j][k] = INF;
}
bool update(int x, int y,int k,int d) // 点坐标x，y，上一步的状态，上一步的代价
{
    if (x < 0 || x >= 6 || y < 0 || y >= 6) return false;
    int cost = k * a[x][y]; // 上一步的状态乘以该位置的数值
    int pos = cost % 4 + 1;
    if (dp[x][y][pos] > d + cost)
    {
        dp[x][y][pos] = d + cost;
        return true;
    }
    return false;
}
void guihua(int x, int y,int k,int d)
{
    if (update(x - 1, y, k, d)) guihua(x - 1, y, k * a[x - 1][y] % 4 + 1, d + k * a[x - 1][y]);
    if (update(x + 1, y, k, d)) guihua(x + 1, y, k * a[x + 1][y] % 4 + 1, d + k * a[x + 1][y]);
    if (update(x, y - 1, k, d)) guihua(x, y - 1, k * a[x][y - 1] % 4 + 1, d + k * a[x][y - 1]);
    if (update(x, y + 1, k, d)) guihua(x, y + 1, k * a[x][y + 1] % 4 + 1, d + k * a[x][y + 1]);
}

int main()
{
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
            cin >> a[i][j];
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    initial();
    dp[sx][sy][1] = 0;
    guihua(sx, sy, 1, 0);
    int m = dp[ex][ey][1];
    for (int i = 2; i <= 4; i++)
        m = min(m, dp[ex][ey][i]);
    cout << m << endl;
}