Zoj 2634 Collecting Stones


		题目大意:
一张8x8的格子图,每个格子有不超过2000001个石头,从(1,1)走到(8,8),走过的格子不能再走且只能向上,下,右,右上,右下,5个方向走,问走到(8,8)时是否能刚好收集M个石头.
 
题目思路:
dp神马的没想法.
走暴力深搜路线,单纯的肯定不行.
试着剪枝.
剪枝一:当前累加和大于m跳出,走其他路,这个好想.
剪枝二:当前累加和+所在列之后的所有和小于m,跳出.
剪枝二很重要! 为什么,不知道...
 
代码:
[cpp]  
#include <stdlib.h>  
#include <string.h>  
#include <stdio.h>  
#include <ctype.h>  
#include <math.h>  
#include <stack>  
#include <queue>  
#include <map>  
#include <set>  
#include <vector>  
#include <string>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
  
#define ll long long  
#define ls rt<<1  
#define rs ls|1  
#define lson l,mid,ls  
#define rson mid+1,r,rs  
#define middle (l+r)>>1  
#define eps (1e-8)  
#define clr_all(x,c) memset(x,c,sizeof(x))  
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))  
#define MOD 1000000007  
#define INF 0x3f3f3f3f  
#define PI (acos(-1.0))  
#define _mod(x,y) ((x)>0? (x)%(y):((x)%(y)+(y))%(y))  
#define _abs(x) ((x)<0? (-(x)):(x))  
#define getmin(x,y) (x= ((x)<0 || (y)<(x))? (y):(x))  
#define getmax(x,y) (x= ((y)>(x))? (y):(x))  
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}  
template <class T> T _max(T x,T y){return x>y? x:y;}  
template <class T> T _min(T x,T y){return x<y? x:y;}  
int TS,cas=1;  
const int M=1000+5;  
bool flag;  
int m,vis[11][11],a[11][11],dp[11];  
int dir[5][2]={{1,0},{-1,0},{1,1},{-1,1},{0,1}};  
int tot;  
  
void dfs(int x,int y){  
    if(tot>m) return;  
    if(x==y && x==8){  
        if(tot==m) flag=true;  
        return;  
    }  
    for(int i=0;i<5;i++){  
        int xx=x+dir[i][0],yy=y+dir[i][1];  
        if(xx<1 || yy<1 || xx>8 || yy>8) continue;  
        if(vis[xx][yy] || tot+dp[y]<m) continue;  
        vis[xx][yy]=1;  
        tot+=a[xx][yy];  
        dfs(xx,yy);  
        if(flag) return;  
        tot-=a[xx][yy];  
        vis[xx][yy]=0;  
    }  
}  
  
void run(){  
    int i,j;  
    scanf("%d",&m);  
    for(i=1;i<=8;i++)  
        for(j=1;j<=8;j++)  
            scanf("%d",&a[i][j]);  
    clr_all(dp,0);  
    for(i=1;i<=8;i++)  
        for(j=1;j<=8;j++)  
            dp[j]+=a[i][j];  
    for(i=7;i>0;i--)  
        dp[i]+=dp[i+1];  
    clr_all(vis,0);  
    tot=a[1][1],vis[1][1]=1;  
    flag=0,dfs(1,1);  
    printf("%s\n",flag? "Yes":"No");  
}  
  
void preSof(){  
}  
  
int main(){  
    //freopen("input.txt","r",stdin);  
    //freopen("output.txt","w",stdout);  
    preSof();  
    //run();  
    //while(~scanf("%d%d",&n,&q)) run();  
    for(scanf("%d",&TS);cas<=TS;cas++) run();  
    return 0;  
}

补充：软件开发 , C++ ,