机器人系列2

Time Limit: 2000/1000 MS ( Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 996 Accepted Submission(s): 185

Problem Description 这又是一个简单的游戏，你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下：
1.机器人一开始在棋盘的起始点(1,1)并有起始点所标有的能量。
2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。
3.只有当机器人消耗完能量时才能获得相应格子上的能量。
请问机器人到达终点的过程中最多有几次完全消耗完能量，消耗完这么多次能量的方式有几种。
Input 输入
第一行输入一个整数T,表示数据的组数。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。

Output 请问机器人到达终点的过程中最多有几次完全消耗完能量，消耗完这么多次能量的方式有几种。
Sample Input

1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2

Sample Output

3 4

思路：每个点应该要能记录的当前状态为：1，到达此点过程中消耗完能量的最多次数 2，符合1中条件的路线数一个点把能量耗尽能到达一些点，对这些点要做这些处理：（假设从a走到b） 1，如果到达 a点的 能量耗完的次数加一和 b点记录的 能量耗完次数相同，那么把 a路线数加到b中 2，如果到达 a点的 能量耗完的次数加一大于 b点记录的次数，那么重新记录 b点信息，即 b中能量耗完最多次数 增加到a的次数加一， 路线数为 a中的 路线数 还有一种特解情况，那就是当前点的能量能走到终点却没有耗完，那么直接不用加一进行上面的操作

#include
using namespace std;
int n,m,map[111][111];
struct node
{
int num1,num2; //到达当前点状态，num1：耗完能量的最多次数，num2：满足num1的路线数
}ss[111][111];
void add(int x,int y,int xx,int yy,int k) //从（x，y）走到（xx，yy），k：标记此次移动能量是否耗完
{
if(ss[xx][yy].num1==ss[x][y].num1+k) //相等则把路线数加上来
ss[xx][yy].num2+=ss[x][y].num2;
if(ss[xx][yy].num1 {
ss[xx][yy].num1=ss[x][y].num1+k;
ss[xx][yy].num2=ss[x][y].num2;
}
}
int main (void)
{
int t,i,j,k,l,x,y,xx,yy,v;
cin>>t;
while(t--&&cin>>n>>m)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>map[i][j];
ss[i][j].num1=ss[i][j].num2=0;
}
ss[1][1].num2=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(!ss[i][j].num2)continue; //为了优化，只要对先前到达过的点进行移动处理
l=i+j+map[i][j]; //判断当前点能走的最远距离
if(!map[i][j]||i==n&&j==m)continue; //如果当前点能量为0或者是终点，那么不用处理
if(l>=n+m) //如果能走的最远距离大于或等于走到终点的距离，即能走到终点
{
add(i,j,n,m,(l==n+m) 1:0); //如果走到终点能量耗完，则标记1
continue;
}
for(k=i;k<=l;k++) //遍历当前点右下方能走到的那些点
{
if(k<=n&&l-k<=m&&l-k>=j) //不出界
{
add(i,j,k,l-k,1);
}
}
}
cout< }
return 0;
}

HDU--1876--机器人系列2--DP

机器人系列2