1358 棋盘游戏[状压dp]

1358 棋盘游戏

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 大师 Master

查看运行结果

题目描述 Description

这个游戏在一个有10*10个格子的棋盘上进行，初始时棋子位于左上角，终点为右下角，棋盘上每个格子内有一个0到9的数字，每次棋子可以往右方或下方的相邻格子移动，求一条经过数字之和最小且经过0到9的所有数字的合法路径，输出其长度。（经过的数字包括左上角和右下角）

输入描述 Input Description

输入包含10行，每行10个数字，以空格隔开，表示棋盘格子上的权值。数据保证存在合法路径。

输出描述 Output Description

输出所求路径的权值和。

样例输入 Sample Input

0 1 2 3 4 5 6 7 8 9

1 1 1 1 1 1 1 1 1 0

2 1 1 1 1 1 1 1 1 0

3 1 1 1 1 1 1 1 1 0

4 1 1 1 1 1 1 1 1 0

5 1 1 1 1 1 1 1 1 0

6 1 1 1 1 1 1 1 1 0

7 1 1 1 1 1 1 1 1 0

8 1 1 1 1 1 1 1 1 0

9 1 1 1 1 1 1 1 1 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例解释】

先一直向右走到第一行末尾，再竖直向下走位最优路径。

分类标签 Tags 点此展开

动态规划状态压缩型DP

#include<cstdio>

#include<cstring>

#include<iostream>

#define EF if(ch==EOF) return x;

using namespace std;

const int N=;

int n,g[N][N],f[<<N][N][N];

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;EF;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//f[S][i][j]已经走过S集合中的点(0-9),当前在(i,j)的最小花费

void dp(){

    memset(f,0x3f,sizeof f);

    f[<<g[][]][][]=g[][];

    for(int S=;S<(<<);S++){

        for(int i=;i<=n;i++){

            for(int j=;j<=n;j++){

                if(S&(<<g[i][j]))

                    f[S|(<<g[i+][j])][i+][j]=min(f[S|(<<g[i+][j])][i+][j],f[S][i][j]+g[i+][j]),

                    f[S|(<<g[i][j+])][i][j+]=min(f[S|(<<g[i][j+])][i][j+],f[S][i][j]+g[i][j+]);

            }

        }

    }

    printf("%d\n",f[(<<)-][n][n]);

}

int main(){

    n=;

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            g[i][j]=read();

        }

    }

    dp();

    return ;

}

巴特西

1358 棋盘游戏[状压dp]

1358 棋盘游戏

分类标签 Tags 点此展开

最新文章

热门文章