暑期集訓(xùn)開始啦~因為是第一天，所以還沒有正式開始講座什么的，下午是一個小訓(xùn)練。

題目主要是深搜廣搜，難度不大，但是我為了以后日更墊個底，先更兩題深搜壓壓驚~

?

ZOJ 2100 Seeding

題目大意：S是不能走得，剩下的.要一筆畫完，問是否可以實現(xiàn)。

我的思路：一本正經(jīng)的深搜啊，都寫在備注里啦~

?

#include <stdio.h> char a[10][10]; int n,m,i,j,z[4][2]={0,1,0,-1,1,0,-1,0},re,sum;//四個方向 void dfs(int x,int y,int ss) {if(x>=n||y>=m||x<0||y<0)return;//出界 int i,xx,yy;for(i=0;i<4;i++){xx=x+z[i][0];yy=y+z[i][1];if(a[xx][yy]!='S'){if(ss==n*m-sum-1)//走完啦~ {re=1;return;}a[xx][yy]='S';//標(biāo)記 dfs(xx,yy,ss+1);a[xx][yy]='.';//復(fù)原，方便下次深搜 }}return; } int main() { while(scanf("%d%d",&n,&m)){sum=0;if(n==0&&m==0)break;for(i=0;i<n;i++){scanf("%s",a[i]);for(j=0;j<m;j++){if(a[i][j]=='S')sum++;}}a[0][0]='S';re=0;dfs(0,0,0); if(re)printf("YES\n");else printf("NO\n");} }

?

?

ZOJ 2110 Tempter of the Bone?

?

?

題目大意：（參照樣例一）給出4*4的地圖，從S走到D，5步是否恰好可以，是正好五步，所以可以繞完為了滿足這個5的哦。

我的思路：還是 一本正經(jīng) 的 深搜呀...不過這里剪枝了一下，更快一些，深搜的函數(shù)里也可以剪。

?

#include <stdio.h> char a[10][10]; int n,m,s,i,j,z[4][2]={0,1,0,-1,1,0,-1,0},sx,sy,dx,dy,wall,re;//四個方向 void dfs(int x,int y,int ss) {if(x>=n||y>=m||x<0||y<0)return;//出界 if(ss==s&&x==dx&&y==dy) re=1;//走到目的地 if(re)return;int i,xx,yy;for(i=0;i<4;i++){xx=x+z[i][0];yy=y+z[i][1];if(a[xx][yy]!='X'){a[xx][yy]='X';//標(biāo)記 dfs(xx,yy,ss+1);a[xx][yy]='.';//復(fù)原 }}return; } int main() { while(scanf("%d%d%d",&n,&m,&s)){wall=0;if(n==0&&m==0&&s==0)break;for(i=0;i<n;i++){scanf("%s",a[i]);for(j=0;j<m;j++){ if(a[i][j]=='S')sx=i,sy=j;if(a[i][j]=='D')dx=i,dy=j;if(a[i][j]=='X')wall++;}}if(n*m-wall<=s){printf("NO\n");continue;}a[sx][sy]='X';re=0;dfs(sx,sy,0); if(re)printf("YES\n");else printf("NO\n");} }

?

?

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的ACM 深搜 SeedingTempter of the Bone的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。