Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 32768/65536 K
(Java/Others)
Total Submission(s): 754 Accepted
Submission(s): 264
Special
Judge
题意：
做了这题后告诉我一个真理，题意真的很重要！！
开始WA以为自己搞错题意了，然后上网看别人解题报告里的题意，让我迷惑的就是在边界的撞过去会怎样，- -本来是觉得应该会飞出去，这样挺好的~~
后来忘了是什么原因错了，一直TLE，就怀疑这个想法(好像没关系...)，看到别人的是不能有这种情况，就按此思路再写再改，后来还是一直WA；于是再看一解题报告，
发现本来的才是对的：http://www.2cto.com/kf/201208/149755.html
题意大概如此，有然若干个可能叠起的方格放在某些格子上，选择任意点作为始点，Pusher可以沿某方向前进把格子推向正对方向的前一格，每次能减少1个，如果前一格有方格就叠起，如果前面一格已出界，就全部推掉了，减少n个。求一个可行解的始点及其操作。
dfs：
弄清楚提议后就好写了，弄了半天，心力交瘁= =我的代码可以优化，不过暂时不想看它了。
暴力n*m个点然后深搜可行解！
1 //15MS 240K 2251 B G++ 2 #include<stdio.h> 3 #include<string.h> 4 char c[5]="RDLU"; 5 int mov[4][2]={0,1,1,0,0,-1,-1,0}; 6 char g[30][30]; 7 char root[10000]; 8 int n,m,flag,sum; 9 int sx,sy; 10 int judge(int x,int y) 11 { 12 if(x>=0&&x<n&&y>=0&&y<m) return 1; 13 return 0; 14 } 15 void dfs(int x,int y,int cnt,int s) 16 { 17 if(flag) return; 18 if(sum==s){ 19 flag=1; root[cnt]=‘\0‘; return; 20 } 21 for(int i=0;i<4;i++){ 22 int tx=x+mov[i][0]; 23 int ty=y+mov[i][1]; 24 if(!judge(tx,ty) || g[tx][ty]) continue; 25 while(judge(tx,ty) && !g[tx][ty]){ 26 tx+=mov[i][0];ty+=mov[i][1]; 27 } 28 if(judge(tx,ty) && g[tx][ty]){ 29 int ta=tx+mov[i][0]; 30 int tb=ty+mov[i][1]; 31 root[cnt]=c[i]; 32 int temp=g[tx][ty]; 33 if(g[tx][ty]==1){ 34 g[tx][ty]=0; 35 dfs(tx,ty,cnt+1,s+1); 36 if(flag) return; 37 g[tx][ty]=1; 38 }else{ 39 if(judge(ta,tb)){ 40 g[ta][tb]+=temp-1; 41 g[tx][ty]=0; 42 dfs(tx,ty,cnt+1,s+1); 43 if(flag)return; 44 g[ta][tb]-=temp-1; 45 g[tx][ty]=temp; 46 }else{ 47 g[tx][ty]=0; 48 dfs(tx,ty,cnt+1,s+temp); 49 if(flag)return; 50 g[tx][ty]=temp; 51 } 52 } 53 } 54 } 55 return; 56 } 57 int main(void) 58 { 59 while(scanf("%d%d",&m,&n)!=EOF) 60 { 61 int i,j; 62 flag=0; 63 sum=0; 64 memset(g,0,sizeof(g)); 65 memset(root,0,sizeof(root)); 66 for(i=0;i<n;i++){ 67 scanf("%s",g[i]); 68 for(j=0;j<m;j++){ 69 if(g[i][j]==‘.‘) g[i][j]=0; 70 else{ 71 g[i][j]=g[i][j]-‘a‘+1; 72 sum+=g[i][j]; 73 } 74 } 75 } 76 for(i=0;i<n;i++) if(!flag) 77 for(int j=0;j<m;j++){ 78 sx=i;sy=j; 79 if(!g[i][j]) 80 dfs(i,j,0,0); 81 if(flag){ 82 printf("%d\n%d\n",i,j); 83 puts(root); 84 break; 85 } 86 } 87 } 88 return 0; 89 } 90 /* 91 3 92 7 93 ... 94 ... 95 .b. 96 ... 97 ... 98 .a. 99 ... 100 */
hdu 2821 Pusher (dfs),布布扣,bubuko.com
原文：http://www.cnblogs.com/GO-NO-1/p/3617615.html