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 1500 using namespace std;
int g[][],f[][][maxn],ans; int min(int x,int y){return x<y?x:y;} int main()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
scanf("%d",&g[i][j]);
memset(f,/,sizeof(f));
f[][][<<g[][]]=g[][];
int mxx=<<,SS;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int S=;S<mxx;S++){
SS=S|(<<g[i+][j]);
f[i+][j][SS]=min(f[i+][j][SS],f[i][j][S]+g[i+][j]);
SS=S|(<<g[i][j+]);
f[i][j+][SS]=min(f[i][j+][SS],f[i][j][S]+g[i][j+]);
}
printf("%d\n",f[][][mxx-]);
return ;
}