首页 > 代码库 > codevs1358棋盘游戏(状压dp)

codevs1358棋盘游戏(状压dp)

2024-10-11 15:19:01   208人阅读

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

50

数据范围及提示 Data Size & Hint

【样例解释】

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

 

/*三维状压dp 转移的时候分步即可棋盘只需要放0~9个数字,所以最多只有111111111这样的的状态输出别忘减一(减一才是111111111) */#include<cstdio>#include<cstring>#define maxn 1500using namespace std;int g[12][12],f[12][12][maxn],ans;int min(int x,int y){return x<y?x:y;}int main(){    for(int i=1;i<=10;i++)        for(int j=1;j<=10;j++)            scanf("%d",&g[i][j]);    memset(f,127/3,sizeof(f));    f[1][1][1<<g[1][1]]=g[1][1];    int mxx=1<<10,SS;    for(int i=1;i<=10;i++)        for(int j=1;j<=10;j++)            for(int S=0;S<mxx;S++){                SS=S|(1<<g[i+1][j]);                f[i+1][j][SS]=min(f[i+1][j][SS],f[i][j][S]+g[i+1][j]);                SS=S|(1<<g[i][j+1]);                f[i][j+1][SS]=min(f[i][j+1][SS],f[i][j][S]+g[i][j+1]);            }    printf("%d\n",f[10][10][mxx-1]);    return 0; }

 

codevs1358棋盘游戏(状压dp)


联系
我们