为什么暴力bfs搜索都不行，样例都不过????
wa的代码。
View Code
1 /* 2 bfs 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 #include<map> 11 #include<vector> 12 #include<math.h> 13 using namespace std; 14 typedef long long ll; 15 //typedef __int64 int64; 16 const int maxn = 105; 17 const int inf = 99999999; 18 const int CLEAR = 0x7F; 19 const double pi=acos(-1.0); 20 const double eps = 1e-8; 21 22 const int dx[]={1,0}; 23 const int dy[]={0,1}; 24 int mat[ maxn ][ maxn ]; 25 struct node{ 26 int x,y,energe,ti; 27 }; 28 int ans1,ans2; 29 void bfs( int n,int m ){ 30 queue<node>q; 31 while( !q.empty() ) q.pop(); 32 node now,nxt; 33 now.x = now.y = 1; 34 now.energe = mat[ 1 ][ 1 ]; 35 if( now.energe<=0 ){ 36 ans1=ans2=0; 37 return ; 38 } 39 now.ti = 0; 40 q.push( now ); 41 ans1 = -inf;//到达终点前有ans1次消耗完能量 42 ans2 = 0;//消耗这么多能量有多少次 43 while( !q.empty() ){ 44 now = q.front(); 45 q.pop(); 46 if( now.x==n&&now.y==m ){ 47 if( now.ti>ans1 ){ 48 ans1 = now.ti; 49 ans2 = 1; 50 } 51 else if( now.ti==ans1 ){ 52 ans2++; 53 } 54 } 55 for( int k=0;k<2;k++ ){ 56 nxt = now; 57 nxt.x = now.x+dx[ k ]; 58 nxt.y = now.y+dy[ k ]; 59 if( nxt.x>0&&nxt.x<=n&&nxt.y>0&&nxt.y<=m ){ 60 nxt.energe--; 61 if( nxt.energe==0 ){ 62 nxt.energe += mat[nxt.x][nxt.y]; 63 nxt.ti++; 64 if( nxt.energe <=0 ) continue; 65 } 66 q.push( nxt ); 67 } 68 } 69 } 70 if( ans1==inf ) ans1=ans2=0; 71 return ;//ans2; 72 } 73 74 int main(){ 75 int ca; 76 scanf("%d",&ca); 77 while( ca-- ){ 78 int n,m; 79 scanf("%d%d",&n,&m); 80 for( int i=0;i<n;i++ ){ 81 for( int j=0;j<m;j++ ){ 82 scanf("%d",&mat[ i ][ j ]); 83 } 84 } 85 bfs( n,m ); 86 printf("%d %d\n",ans1,ans2); 87 } 88 return 0; 89 }
之后再用dp+记忆化搜索
首先用sum记录从起点的到终点的0出现的次数，num记录出现sum这么多次数的0的方法数。。
然后初始化 起点 sum=0，num=1（起点不为0，所以只有1种方法到0）
当某时刻的位置为i，j时，又知当前的距离now_time，所以必须直接从 i，j 一次性走这么多距离，其中没走到的点可以忽略
不会对结果产生影响。。
注意在更新ans1 ans2 时候，每次只能更新一次。。
View Code
1 /* 2 dp+记忆化搜索 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 #include<map> 11 #include<vector> 12 #include<math.h> 13 using namespace std; 14 typedef long long int64; 15 //typedef __int64 int64; 16 const int maxn = 105; 17 int mat[ maxn ][ maxn ]; 18 int num[ maxn ][ maxn ];//从00到ij的sum[i][j]这个次数的方法数 19 int sum[ maxn ][ maxn ];//从00到ij的过程中变为0的最多次数 20 void solve( int n,int m ){ 21 memset( sum,0,sizeof( sum ) ); 22 memset( num,0,sizeof( num ) ); 23 int ans1,ans2; 24 ans1=ans2=0; 25 sum[ 1 ][ 1 ] = 0; 26 num[ 1 ][ 1 ] = 1; 27 for( int i=1;i<=n;i++ ){ 28 for( int j=1;j<=m;j++ ){ 29 int now_time = mat[ i ][ j ]; 30 if( now_time == 0 ) continue; 31 if( num[ i ][ j ]==0 ) continue; 32 if( i==n&&j==m ) continue; 33 34 int flag = 1; 35 for( int k=0;k<=now_time;k++ ){ 36 int tx = i+k; 37 int ty = j+now_time-k; 38 39 if( n-i+m-j<=now_time&&flag == 1 ){ 40 //printf("i:%d j:%d\n",i,j); 41 int tmax = sum[ i ][ j ]; 42 if( n-i+m-j==now_time ) tmax++; 43 if( tmax>ans1 ){ 44 ans1 = tmax; 45 ans2 = num[ i ][ j ]; 46 } 47 else if( tmax==ans1 ) ans2 += num[i][j]; 48 flag = -1; 49 }//表示从当前ij点能走到nm这个终点。但是这个只能走一次，否则ans2+=。。这个会重复运行多次 50 51 if( tx<1||tx>n||ty<1||ty>m ) continue; 52 if( sum[ tx ][ ty ]<=sum[ i ][ j ]+1 ){ 53 if( sum[tx][ty]==1+sum[i][j] ){ 54 num[tx][ty]+=num[i][j]; 55 } 56 else{ 57 num[tx][ty] = num[i][j]; 58 sum[tx][ty] = sum[i][j]+1; 59 } 60 } 61 } 62 63 } 64 } 65 66 printf("%d %d\n",ans1,ans2); 67 } 68 69 int main(){ 70 int ca; 71 scanf("%d",&ca); 72 while( ca-- ){ 73 int n,m; 74 scanf("%d%d",&n,&m); 75 for( int i=1;i<=n;i++ ){ 76 for( int j=1;j<=m;j++ ){ 77 scanf("%d",&mat[ i ][ j ]); 78 } 79 } 80 solve( n,m ); 81 } 82 return 0; 83 }