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++ ,
