2015 UESTC Training for Dynamic Programming J

J - 男神的约会

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

有一天男神约了学姐姐去看电影，电影院有一个活动，给你一个10*10的矩阵，每一个格子上都有一个0-9的整数，表示一共十种优惠券中的一种。

观众从左上角的格子开始走，走到右下角。每走到一个有着a号优惠券的格子，都必须要玩一个a分钟的游戏来领取这张优惠券。

每次只能向右或向下走。当走到右下角的时候，如果集齐10种优惠券就可以半价看电影呢。

为了能在学姐姐面前展示自己的才智，男神准备用最少的时间领取全部的优惠券(他要省出最多的时间陪学姐姐)。聪明的你能告诉男神，他最少要花费的时间是多少？

Input

输入包含10行，每行10个数字，以空格隔开，表示格子上的优惠券的种类。数据保证存在合法路径。

Output

输出男神走到右下角的最小时间花费。

Sample input and output

Sample Input	Sample Output
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	50

Sample Input

Sample Output

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

解题思路：

　　看到这题后感觉是状压，但是自己状压还没怎么学好，，然后想到了bfs，我每次扩展的时候，把遍历过123456789的node的sum记录下来，然后我们入队更新

最小的sum就好了，，其他跟模板一个样，但一开始答案没跑出来，因为我每次在进入的时候newnode的book没有得到有力的更新。。。

代码：

  1 # include<cstdio>
  2 # include<iostream>
  3 # include<fstream>
  4 # include<algorithm>
  5 # include<functional>
  6 # include<cstring>
  7 # include<string>
  8 # include<cstdlib>
  9 # include<iomanip>
 10 # include<numeric>
 11 # include<cctype>
 12 # include<cmath>
 13 # include<ctime>
 14 # include<queue>
 15 # include<stack>
 16 # include<list>
 17 # include<set>
 18 # include<map>
 19 
 20 using namespace std;
 21 
 22 const double PI=4.0*atan(1.0);
 23 
 24 typedef long long LL;
 25 typedef unsigned long long ULL;
 26 
 27 # define inf 999999999
 28 
 29 int grid[10][10];
 30 int nxt[2][2] = {{1,0},{0,1}};
 31 
 32 struct node
 33 {
 34     int x,y;
 35     int sum;
 36     int book[10];
 37     node()
 38     {
 39         memset(book,0,sizeof(book));
 40     }
 41 };
 42 
 43 
 44 
 45 int check ( node state )
 46 {
 47     for ( int i = 0;i < 10;i++ )
 48     {
 49         if ( state.book[i]==0 )
 50         {
 51             return 0;
 52         }
 53     }
 54     return 1;
 55 }
 56 
 57 
 58 
 59 int can_move ( int x,int y )
 60 {
 61     if ( x>=0&&x<10&&y>=0&&y<10 )
 62         return 1;
 63     else
 64         return 0;
 65 }
 66 
 67 
 68 
 69 int bfs ( node start )
 70 {
 71 
 72     int mn = inf;
 73     queue<node>Q;
 74     Q.push(start);
 75     while ( !Q.empty() )
 76     {
 77         node now = Q.front();
 78         Q.pop();
 79         for ( int i = 0;i < 2;i++ )
 80         {//extend
 81             int tx = now.x+nxt[i][0], ty = now.y+nxt[i][1];
 82             if ( can_move(tx,ty) )
 83             {
 84                 node newnode = now;
 85                 newnode.x = tx; newnode.y = ty; newnode.sum = now.sum+grid[tx][ty]; newnode.book[grid[tx][ty]]=1;
 86                 if ( newnode.x==9&&newnode.y==9 )
 87                 {
 88                     if ( check(newnode)&&newnode.sum < mn )
 89                     {
 90                         mn = newnode.sum;
 91                     }
 92                 }
 93                 Q.push(newnode);
 94             }
 95         }
 96     }
 97 
 98     return mn;
 99 }
100 
101 
102 int main(void)
103 {
104 
105     for ( int i = 0;i < 10;i++ )
106     {
107         for ( int j = 0;j < 10;j++ )
108         {
109             scanf("%d",&grid[i][j]);
110         }
111     }
112 
113     node start;
114     start.x = 0; start.y = 0; start.sum = grid[0][0]; start.book[grid[0][0]]=1;
115     int ans = bfs(start);
116     printf("%d
",ans);
117 
118     return 0;
119 }