表示这题坑了我很久，我拿到题目马上想到的是用记忆化搜索做， 然后发现不是很好实现 ，然后又想了一种 半记忆化+BFS 的东西，当时分析了下发现可行。 然后写了很久， 最后死都过不了。 然后看了别人的发现别人用的是dp解法，和我的非常类似，然后我用dp那样写发现能过， 最后调试了一晚上后终于发现了，用BFS还是难是实现。 有一些数据用bfs做会错。
以前总是以为用dp能写的东西，那记忆化搜索也会很好写， 今天终于发现不用的方法还是要因题而议 ！ ， 所以以后别看这能用搜索做就立马什么都不想就用搜索做。
机器人系列2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 866 Accepted Submission(s): 153
Problem Description
这又是一个简单的游戏，你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下：
1.机器人一开始在棋盘的起始点(1,1)并有起始点所标有的能量。
2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。
3.只有当机器人消耗完能量时才能获得相应格子上的能量。
请问机器人到达终点的过程中最多有几次完全消耗完能量，消耗完这么多次能量的方式有几种。
1.机器人一开始在棋盘的起始点(1,1)并有起始点所标有的能量。
2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。
3.只有当机器人消耗完能量时才能获得相应格子上的能量。
请问机器人到达终点的过程中最多有几次完全消耗完能量，消耗完这么多次能量的方式有几种。
Input
输入
第一行输入一个整数T,表示数据的组数。
对于每一组数据第一行输入两个整数n,m(1 <= n,m <= 100)。表示棋盘的大小。接下来输入n行,每行m个整数e(0 <= e < 20)。
第一行输入一个整数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
Author
xhd
Source
Recommend
lcy
AC CODE
#include <stdio.h> #include <queue> #include <string.h> #include <iostream> using namespace std; #define N 110 typedef unsigned __int64 LL; struct node { LL x,y; }; int n,m; LL g[N][N]; LL mark[N][N]; LL num[N][N]; LL sum[N][N]; void bfs()// 最后发现用bfs漏洞很多. 同时也说明有些用dp很容易解决的问题用搜索做也会变得比较复杂. { // 因为这题的状态转移很是纠结. 涉及到了加和. 用dfs 就会出现很多重复的. 从而导致加和的时候出现了问题. // 而用dp的话，简单好写而且很准确。 所以以后遇到这种满足dp性质的。 尽量选择dp解. 实在不行在用搜索. int a=0,b=1; LL mx=0; LL mxcnt=0; memset(num,0,sizeof(num)); memset(mark,0,sizeof(mark)); memset(sum,0,sizeof(sum)); //queue<node> que[2]; node tmp; tmp.x=1; tmp.y=1; // que[0].push(tmp); num[1][1]=1; // 用来记录达到这个次数有多少种方法 mark[1][1]=1;// 用来标记 sum[1][1]=0; // 用来记录次数 node cur; for(cur.x=1;cur.x<=n;cur.x++) for(cur.y=1;cur.y<=m;cur.y++) // 想了想还是不好弄的. { // node cur=que[b].front(); // que[b].pop(); // mark[cur.x][cur.y]=0; // 表示这个位置已经取出 int k=g[cur.x][cur.y]; if(cur.x==n&&cur.y==m) continue; if(num[cur.x][cur.y]==0) continue; if(k==0) continue; if(n-cur.x+m-cur.y<=k) { LL tnum = sum[cur.x][cur.y]; if( n-cur.x+m-cur.y==k ) { tnum++; } if( tnum > mx) { mx = tnum; mxcnt=num[cur.x][cur.y]; } else if(tnum==mx) mxcnt += num[cur.x][cur.y]; continue; } for(int i=0;i<=k;i++) { int cx=cur.x+i; int cy=cur.y+k-i; if( (cx>=1&&cx<=n)&&(cy>=1&&cy<=m) && g[cx][cy]!=0 ) { node nwnode; nwnode.x=cx; nwnode.y=cy; if( sum[cur.x][cur.y]+1 >= sum[cx][cy] ) { if( sum[cur.x][cur.y]+1 == sum[cx][cy] ) { num[cx][cy] += num[cur.x][cur.y]; } else { sum[cx][cy] = sum[cur.x][cur.y]+1; num[cx][cy] = num[cur.x][cur.y]; } /* if( mark[cx][cy]==0 ) { mark[cx][cy]=1; que[a].push(nwnode); }*/ } } } } printf("%I64d %I64d\n",mx,mxcnt); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%I64d",&g[i][j]); bfs(); } return 0; }
BFS 不能ac的
#include <stdio.h> #include <queue> #include <string.h> #include <iostream> using namespace std; #define N 110 typedef __int64 LL; struct node { int x,y; }; int n,m; int g[N][N]; int mark[N][N]; LL num[N][N]; LL sum[N][N]; void bfs() { int a=0,b=1; LL mx=0; LL mxcnt=0; memset(num,0,sizeof(num)); memset(mark,0,sizeof(mark)); memset(sum,0,sizeof(sum)); queue<node> que[2]; while(que[0].size()!=0) que[0].pop(); while(que[1].size()!=0) que[1].pop(); node tmp; tmp.x=1; tmp.y=1; que[0].push(tmp); num[1][1]=1; // 用来记录达到这个次数有多少种方法 mark[1][1]=1;// 用来标记 sum[1][1]=0; // 用来记录次数 while(que[a].size()!=0) { swap(a,b); while(que[b].size()!=0) { node cur=que[b].front(); que[b].pop(); mark[cur.x][cur.y]=0; // 表示这个位置已经取出 int k=g[cur.x][cur.y]; for(int i=0;i<=k;i++) { int cx=cur.x+i; int cy=cur.y+k-i; if( (cx>=1&&cx<=n)&&(cy>=1&&cy<=m) && g[cx][cy]!=0 ) { node nwnode; nwnode.x=cx; nwnode.y=cy; if( sum[cur.x][cur.y]+1 >= sum[cx][cy] ) { if( sum[cur.x][cur.y]+1 == sum[cx][cy] ) { num[cx][cy] += num[cur.x][cur.y]; // num 那里有问题. } else { sum[cx][cy] = sum[cur.x][cur.y]+1; num[cx][cy] = num[cur.x][cur.y]; } if( mark[cx][cy]==0 ) { mark[cx][cy]=1; que[a].push(nwnode); } } } } } } for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=m ; j++) { if(num[i][j]==0) continue; if(i==n&&j==m) continue; int k=g[i][j]; if(n-i+m-j<=k) { int tnum = sum[i][j]; if( n-i+m-j==k ) tnum++; if( tnum > mx ) { mx = tnum; mxcnt=num[i][j]; } else if(tnum==mx) mxcnt += num[i][j]; continue; } } printf("%I64d %I64d\n",mx,mxcnt); //bfs1(); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&g[i][j]); bfs(); } return 0; }