sdut 2610 超级坑，但也超级巧妙地减枝

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,m,help[4][2]={1,0,0,1,0,-1,-1,0}; int a[20][20],map_s[20][20]; bool check(int x,int y,int i) { int xx=x+help[i][0],yy=y+help[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m) if(a[xx][yy]) return true; else return false; return true; } int cal(int x,int y,int i) { int xx=x+help[i][0],yy=y+help[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m) return a[xx][yy]; return 6; } void del(int x,int y,int num) { a[x][y]+=num; for(int i=0;i<4;i++) { int xx=x+help[i][0],yy=y+help[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m) a[xx][yy]+=num; } } int flag=0; void dfs(int k) { int x=k/m,y=k%m,i,j; if(flag) return; if(k/m>=n) { for(int i=0;i<m;i++) if(a[n-1][i]) return; flag=1; return; } if(k/m==0) { map_s[x][y]=0; dfs(k+1); if(a[x][y]&&check(x,y,0)&&check(x,y,1)&&check(x,y,2)) { map_s[x][y]=1; del(x,y,-1); dfs(k+1); if(flag) return; del(x,y,1); } } else { int tp=cal(x,y,3); if(tp>1) return; else { if(tp) { if(a[x][y]>0&&cal(x,y,0)>0&&cal(x,y,1)>0&&cal(x,y,2)>0) { map_s[x][y]=1; del(x,y,-1); dfs(k+1); if(flag) return; del(x,y,1); } } else { map_s[x][y]=0; dfs(k+1); if(flag) return; } } } } int main() { int t,i,j,cas=0; scanf("%d",&t); while(t--&&scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("",&a[i][j]); flag=0; memset(map_s,-1,sizeof(map_s)); dfs(0); printf("Case %d:\n",++cas); for(i=0;i<n;i++) { for(j=0;j<m;j++) printf("%c",map_s[i][j]?'*':'.'); printf("\n"); } } return 0; } /* 1 2 2 11 22 */