這次的題目叫圖的深度&&廣度優先遍歷。

　　然后等我做完了題發現這是DFS&&BFS爆搜專題。

　　3278：題目是經典的FJ，他要抓奶牛。他和牛（只有一頭）在一條數軸上，他們都站在一個點上（坐標為0~1e5）。假設FJ的位置為x，他每次可以去x+1,x-1,x*2的地方。問他最少走幾次才能抓到他的牛（牛不會動）。

　　赤裸裸的BFS，注意判斷是否越界（很容易RE）

　　CODE

#include<cstdio> #include<cstring> using namespace std; const int N=100000; int q[N*3+10],step[N+5],n,k; bool vis[N+5]; inline void read(int &x) {x=0; char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int main() {read(n); read(k);memset(vis,true,sizeof(vis));if (n>=k) printf("%d",n-k); else{int head=0,tail=1;q[1]=n; step[n]=0; vis[n]=0;while (head<tail){int now=q[++head];if (now==k) { printf("%d",step[now]); break; }if (now+1<=N) if (vis[now+1]) vis[now+1]=0,q[++tail]=now+1,step[now+1]=step[now]+1;if (now-1>=0) if (vis[now-1]) vis[now-1]=0,q[++tail]=now-1,step[now-1]=step[now]+1;if (now*2<=N) if (vis[now*2]) vis[now*2]=0,q[++tail]=now*2,step[now*2]=step[now]+1;}}return 0; }

?

　　2049：一道迷宮BFS，和今年NOIP PJ T3 有點類似。題意可以百度翻譯（這道題翻譯的還是很好的，至少能看懂）

　　因為他給出的是網格的邊而不是點，所以要進行轉化。

　　我們用a[x][y][0]表示（x，y）右方向的邊的屬性（墻或門或空地），a[x][y][1]表示（x，y）上方向的邊的屬性（同理）

　　建圖玩了以后可以再連邊跑SPFA或者直接松弛BFS（循環更新到每個點的的最小通過門數）

　　最后提醒那個人有可能不在迷宮里，就直接輸出0

　　CODE

#include<cstdio> #include<cmath> using namespace std; const int N=205,INF=1e9,fx[4]={0,1,-1,0},fy[4]={1,0,0,-1}; int a[N][N][2],f[N][N],q[N*N*10+10][2],n,m,i,j,x,y,d,t; double s_x,s_y; inline void read(int &x) {x=0; char ch=getchar(); int flag=1;while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();x*=flag; } int main() {for (;;){read(n); read(m);if (n==-1&&m==-1) break;for (i=0;i<N;++i)for (j=0;j<N;++j)f[i][j]=INF,a[i][j][0]=a[i][j][1]=2;for (i=1;i<=n;++i){read(x); read(y); read(d); read(t);if (d) {for (j=y;j<y+t;++j)a[x][j][1]=0;} else{for (j=x;j<x+t;++j)a[j][y][0]=0;}}for (i=1;i<=m;++i){read(x); read(y); read(d);if (d) a[x][y][1]=1; else a[x][y][0]=1;}scanf("%lf%lf",&s_x,&s_y);x=floor(s_x); y=floor(s_y);if (x<0||y<0||x>199||y>199||(!n&&!m)) { puts("0"); continue; }int head=0,tail=1;q[1][0]=x; q[1][1]=y; f[x][y]=0;while (head<tail){x=q[++head][0]; y=q[head][1];for (i=0;i<4;++i){int xx=x+fx[i],yy=y+fy[i];if (xx<0||yy<0||xx>200||yy>200) continue;if (i==0){if (a[xx][yy][0]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];if (a[xx][yy][0]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;} if (i==1){if (a[xx][yy][1]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];if (a[xx][yy][1]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;}if (i==2){if (a[x][y][1]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];if (a[x][y][1]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;}if (i==3){if (a[x][y][0]==2) if (f[xx][yy]>f[x][y]) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y];if (a[x][y][0]==1) if (f[xx][yy]>f[x][y]+1) q[++tail][0]=xx,q[tail][1]=yy,f[xx][yy]=f[x][y]+1;}}}if (f[0][0]==INF) puts("-1"); else printf("%d\n",f[0][0]);}return 0; }

?

　　3083：這是一道神坑題，完美的展示了爆搜的含義。

　　題意是一個圖，S起點，E終點，.是空地，#是墻不能走。問從S到E左優先和右優先以及最短步數是多少。

　　DFS+BFS。BFS最短和簡單，終點的DFS。

　　因為他要求遵循左右的性質，所以方向數組的定義就很玄學了

　　以左優先為例 如果現在的方向是↑，那么優先級就是←↑→↓，其他方向同理（能左轉就左轉，不能轉就向右轉再判斷），右優先同理。

　　因此預處理一下坐標的順序就很水了。

　　CODE

#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=45, l[4][4]= {{3,0,1,2},{0,1,2,3},{1,2,3,0},{2,3,0,1}, }, r[4][4]= {{1,0,3,2},{2,1,0,3},{3,2,1,0},{0,3,2,1}, }, fx[4]={0,-1,0,1},fy[4]={-1,0,1,0}; char a[N][N]; int q[N*N*10+10][2],step[N][N],i,j,n,m,s_x,s_y,e_x,e_y,t,w,l_ans,r_ans,min_ans; bool vis[N][N],flag; inline void read(int &x) {x=0; char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void l_DFS(int x,int y,int w,int s) {if (flag) return;if (x==e_x&&y==e_y) { l_ans=s; flag=1; return; }for (int i=0;i<4;++i){int xx=x+fx[l[w][i]],yy=y+fy[l[w][i]];if (xx<=0||yy<=0||xx>n||yy>m) continue;if (a[xx][yy]=='#') continue;l_DFS(xx,yy,l[w][i],s+1);} } inline void r_DFS(int x,int y,int w,int s) {if (flag) return;if (x==e_x&&y==e_y) { r_ans=s; flag=1; return; }for (int i=0;i<4;++i){int xx=x+fx[r[w][i]],yy=y+fy[r[w][i]];if (xx<=0||yy<=0||xx>n||yy>m) continue;if (a[xx][yy]=='#') continue;r_DFS(xx,yy,r[w][i],s+1);} } inline void BFS(int s_x,int s_y) {memset(step,0,sizeof(step));memset(vis,true,sizeof(vis));int head=0,tail=1;q[1][0]=s_x; q[1][1]=s_y; step[s_x][s_y]=1; vis[s_x][s_y]=0;while (head<tail){int x=q[++head][0],y=q[head][1];if (x==e_x&&y==e_y) { min_ans=step[x][y]; return; }for (int i=0;i<4;++i){int xx=x+fx[i],yy=y+fy[i];if (xx<=0||yy<=0||xx>n||yy>m) continue;if (a[xx][yy]=='#'||!vis[xx][yy]) continue;q[++tail][0]=xx; q[tail][1]=yy; step[xx][yy]=step[x][y]+1; vis[xx][yy]=0;}} } int main() { read(t);while (t--){read(m); read(n);for (i=1;i<=n;++i)for (j=1;j<=m;++j){cin>>a[i][j];if (a[i][j]=='S') s_x=i,s_y=j;if (a[i][j]=='E') e_x=i,e_y=j;}if (s_x==1) w=3; if (s_x==n) w=1; if (s_y==1) w=2; if (s_y==m) w=0;flag=0; l_DFS(s_x,s_y,w,1); flag=0; r_DFS(s_x,s_y,w,1); BFS(s_x,s_y);printf("%d %d %d\n",l_ans,r_ans,min_ans);}return 0; }

?

轉載于:https://www.cnblogs.com/cjjsb/p/8444969.html

總結

以上是生活随笔為你收集整理的POJ 327820493083的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。