| Picking Coins |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Problem description |
| A pack of coins have been divided into piles, each pile has some number Ni (1 <= Ni <= 25) of coins. All the piles have been placed in an area of R rows(1 <= R <= 100) and C columns (1 <= C <= 100).Given a starting location, you have to make your way out of the area and gather as many coins as you can. From the position (r,c) you can only move to (r-1,c+1), (r, c+1), or (r+1,c+1) and endup your way at any edge of the area. If there exist more than one path that can gather the maximum number of coins, make your path the shortest. |
| Input |
| There will be only one testcase in the input file, the first line contains Two space-separated integers, respectively R and C, then followed R lines, Each line contains C space-separated integers in the obvious order, the last few lines each contains two integer which indicate the starting location. |
| Output |
| For each starting location, output the maximum number of coins you could get and the total length of your path in a single line. |
| Sample Input |
3 7 1 2 6 7 0 0 0 3 5 8 0 0 0 0 4 9 0 0 0 0 0 1 1 3 1 3 6 |
| Sample Output |
21 4 28 4 0 1 |
| Judge Tips |
end
/
start-> 1 2 6 7 0 0 0
\ /
3 5-8 0 0 0 0
4 9 0 0 0 0 0
The path above yields 1 + 5 + 8 + 7 = 21 coins, the length of path is 4
|
解题思路:
知道 DP 的人首先就会想到DP, 这里我就是用 DP的, 注意特殊数据
3 7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 1
2 1
3 2
3 6
输出为:
0 1
0 2
0 1
0 1
///// code 2008-4-28
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 100;
struct t_node{
int sum;
int len;
bool bInQue;
t_node& operator =(const t_node &other){
sum = other.sum;
len = other.len;
return *this;
}
};
struct t_queue_node{
int x;
int y;
int len;
t_queue_node(int py=0, int px=0, int plen=1){ y=py; x=px; len=plen; }
};
t_node g_node[MAX][MAX], g_best;
void init_node(int r, int c){
for(int i=0; i<r; i++){
for(int j=0; j<c; j++){
g_node[i][j].sum = 0;
g_node[i][j].len = INT_MAX;
g_node[i][j].bInQue = false;
}
}
}
void update(int sx, int sy, int dx, int dy, int len, int pile[][MAX],
queue<t_queue_node> &qu){
if( !g_node[dy][dx].bInQue ){
qu.push(t_queue_node(dy, dx, len+1));
g_node[dy][dx].bInQue = true;
}
if( (g_node[sy][sx].sum+pile[dy][dx]>g_node[dy][dx].sum) ||
(g_node[sy][sx].sum+pile[dy][dx]==g_node[dy][dx].sum &&
g_node[sy][sx].len+1<g_node[dy][dx].len) ){
g_node[dy][dx].len = g_node[sy][sx].len+1;
g_node[dy][dx].sum = g_node[sy][sx].sum+pile[dy][dx];
}
}
int main(){
int pile[MAX][MAX];
int sx,sy,c,r;
scanf("%d %d",&r,&c);
for(int i=0; i<r; i++){
for(int j=0; j<c; j++)
scanf("%d",&pile[i][j]);
}
while(scanf("%d %d",&sy,&sx)!=EOF){
init_node(r, c);
sx--;
sy--;
queue<t_queue_node> que;
g_node[sy][sx].len = 1;
g_node[sy][sx].sum = pile[sy][sx];
g_node[sy][sx].bInQue = true;
que.push(t_queue_node(sy, sx, 2));
g_best.len = INT_MAX;
g_best.sum = INT_MIN;
t_queue_node tp;
for(bool bEnd; que.size()!=0; ){
tp = que.front();
que.pop();
bEnd = false;
if(tp.x+1<c && tp.y-1>=0)
update(tp.x, tp.y, tp.x+1, tp.y-1, tp.len, pile, que);
else
bEnd = true;
if(tp.x+1<c)
update(tp.x, tp.y, tp.x+1, tp.y, tp.len, pile, que);
else
bEnd = true;
if(tp.x+1<c && tp.y+1<r)
update(tp.x, tp.y, tp.x+1, tp.y+1, tp.len, pile, que);
else
bEnd = true;
if( bEnd && (g_node[tp.y][tp.x].sum>g_best.sum ||
(g_node[tp.y][tp.x].sum==g_best.sum &&
g_node[tp.y][tp.x].len<g_best.len)) )
g_best = g_node[tp.y][tp.x];
}
printf("%d %d\n", g_best.sum, g_best.len);
}
return 0;
}
评论