題目大意: 一張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; }
