首页 > 代码库 > 1358 棋盘游戏[状压dp]

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

50

数据范围及提示 Data Size & Hint

【样例解释】

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

分类标签 Tags 点此展开 

 
动态规划 状态压缩型DP
#include<cstdio>#include<cstring>#include<iostream>#define EF if(ch==EOF) return x;using namespace std;const int N=12;int n,g[N][N],f[1<<N][N][N];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;EF;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}//f[S][i][j]已经走过S集合中的点(0-9),当前在(i,j)的最小花费 void dp(){    memset(f,0x3f,sizeof f);     f[1<<g[1][1]][1][1]=g[1][1];    for(int S=1;S<(1<<10);S++){        for(int i=1;i<=n;i++){            for(int j=1;j<=n;j++){                if(S&(1<<g[i][j]))                    f[S|(1<<g[i+1][j])][i+1][j]=min(f[S|(1<<g[i+1][j])][i+1][j],f[S][i][j]+g[i+1][j]),                    f[S|(1<<g[i][j+1])][i][j+1]=min(f[S|(1<<g[i][j+1])][i][j+1],f[S][i][j]+g[i][j+1]);            }        }    }    printf("%d\n",f[(1<<10)-1][n][n]);}int main(){    n=10;    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            g[i][j]=read();        }    }    dp();    return 0;}

 

1358 棋盘游戏[状压dp]