点击打开链接
poj 2251 duugeon master（三维）
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> #include <string> #include <map> #define Y 0x3f3f3f3f using namespace std; int n,m,z,mark[31][31][31],l; int dir[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}}; char mapp[31][31][31]; struct node{ int x,y,z,step; }u,v; bool judge(int x,int y,int zz){ if(x>=0&&x<n&&y>=0&&y<=m&&zz>=0&&zz<z&&mark[zz][x][y]==0&&mapp[zz][x][y]!='#') return true; return false; } void bfs(int sx,int sy,int sz){ int i; queue<node>q; u.x=sx,u.y=sy,u.z=sz,u.step=0,mark[sz][sx][sy]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); if(mapp[u.z][u.x][u.y]=='E'){ l=1; printf("Escaped in %d minute(s).\n",u.step); return ; } for(i=0;i<6;i++){ v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; v.z=u.z+dir[i][2]; if(judge(v.x,v.y,v.z)){ mark[v.z][v.x][v.y]=1; v.step=u.step+1; q.push(v); } } } } int main() { int i,j,k,sx,sy,sz; while(scanf("%d %d %d",&z,&n,&m)&&z&&n&&m){ getchar(); for(k=0;k<z;k++){ for(i=0;i<n;i++){ for(j=0;j<m;j++){ scanf("%c",&mapp[k][i][j]); if(mapp[k][i][j]=='S') sx=i,sy=j,sz=k; } getchar(); } getchar(); } memset(mark,0,sizeof(mark));l=0; bfs(sx,sy,sz); if(l==0) printf("Trapped!\n"); } return 0; }
hdu 1312 red and black
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; int mark[22][22],n,m,times,dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char mapp[22][22]; struct node{ int x,y,step; }u,v; void bfs(int x,int y){ queue<node>q; int i; u.x=x,u.y=y,u.step=0,mark[u.x][u.y]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); if(mapp[u.x][u.y]=='.'||mapp[u.x][u.y]=='@'){ times++; } for(i=0;i<4;i++){ v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; if(v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&mark[v.x][v.y]==0&&mapp[v.x][v.y]=='.'){ v.step=u.step+1; mark[v.x][v.y]=1; q.push(v); } } } } int main() { int i,j; while(scanf("%d %d",&m,&n)&&m&&n){ getchar(); memset(mark,0,sizeof(mark));times=0; for(i=0;i<n;i++){ for(j=0;j<m;j++) scanf("%c",&mapp[i][j]); getchar(); } for(i=0;i<n;i++) for(j=0;j<m;j++) if(mapp[i][j]=='@') bfs(i,j); printf("%d\n",times); } return 0; }
csu 1511 残缺的棋盘
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; int a1,a2,b1,b2,c1,c2; int mark[10][10],dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,1},{-1,-1},{1,-1},{1,1}}; char mapp[10][10]; struct node{ int x,y,step; }u,v; void bfs(){ queue<node>q; int i; u.x=a1,u.y=a2,u.step=0,mark[u.x][u.y]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); if(u.x==b1&&u.y==b2){ printf("%d\n",u.step); return ; } for(i=0;i<8;i++){ v.x=u.x+dir[i][0]; v.y=u.y+dir[i][1]; if(v.x>0&&v.x<=8&&v.y>0&&v.y<=8&&mark[v.x][v.y]==0){ v.step=u.step+1; mark[v.x][v.y]=1; q.push(v); } } } } int main() { int l=0; while(scanf("%d %d %d %d %d %d",&a1,&a2,&b1,&b2,&c1,&c2)!=EOF){ memset(mark,0,sizeof(mark));l++; mark[c1][c2]=1;///把不能走的点标记就是简单的bfs了 printf("Case %d: ",l); bfs(); } return 0; }
hdu 1702 ACboy need your help agin
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> #include <stack> using namespace std; int main() { int T,i,t,n,m; char s1[30]; char s2[30]; scanf("%d",&T); while(T--){ scanf("%d%*c%s",&n,s1); if(strcmp(s1,"FIFO")==0){ queue<int>q; while(!q.empty()) q.pop(); for(i=0;i<n;i++){ scanf("%s",s2); if(strcmp(s2,"IN")==0){ scanf("%d%*c",&m); q.push(m); } else{ if(q.size()<1){ printf("None\n"); continue; } t=q.front(),q.pop(); printf("%d\n",t); } } } if(strcmp(s1,"FILO")==0){ stack<int>p; while(!p.empty()) p.pop(); for(i=0;i<n;i++){ scanf("%s",s2); if(strcmp(s2,"IN")==0){ scanf("%d%*c",&m); p.push(m); } else{ if(p.size()==0){ printf("None\n"); continue; } t=p.top(),p.pop(); printf("%d\n",t); } } } } return 0; }
hdu 1548 A strange lift
#include <iostream> #include <stdio.h> #include <memory.h> #include <queue> using namespace std; int N, s, t,a[205],mark[205], flag; struct node { int x, step; }n1, n2, m; int main() { int i; while(scanf("%d", &N), N) { if(N == 0) break; scanf("%d %d", &s, &t); for(i = 1; i <= N; i++) scanf("%d", &a[i]); memset(mark,0,sizeof(mark)); flag=0; n1.x = s; n1.step = 0; mark[n1.x] = true; queue<node> Q; Q.push(n1); while(!Q.empty()) { m = Q.front(); Q.pop(); if(m.x == t) //到达目标 { flag=1; printf("%d\n",m.step); break; } n1.x = m.x - a[m.x]; n2.x = m.x + a[m.x]; if(n1.x>0 && n1.x<=t && !mark[n1.x]) //下去的 { n1.step = m.step + 1; mark[n1.x] =1; //标记 Q.push(n1); } if(n2.x>0 && n2.x<=t && !mark[n2.x]) //上去的 { n2.step = m.step + 1; mark[n2.x] = 1; //标记 Q.push(n2); } } if(!flag) printf("-1\n"); } return 0; }hdu 1240 Astreroids
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; char mapp[11][11][11]; int mark[11][11][11],n,times,sx,sy,sz,ex,ey,ez,ff; int dir[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,1},{0,0,-1}}; struct node { int xx,yy,zz,step; }u,v; int bianjie(int x,int y,int z){ if(x>=0&&x<n&&y>=0&&y<n&&z>=0&&z<n&&(mapp[z][x][y]=='O')&&mark[z][x][y]==0) return 1; return 0; } void bfs(int sx,int sy,int sz){ queue<node>q; int i; u.xx=sx,u.yy=sy,u.zz=sz,times=0;mark[sz][sx][sy]=1; q.push(u); while(!q.empty()){ u=q.front(),q.pop(); //printf("%d %d %d %d\n",u.xx,u.yy,u.zz,u.step); if(u.xx==ex&&u.yy==ey&&u.zz==ez){ ff=1;times=u.step;printf("%d %d\n",n,times);return ; } for(i=0;i<6;i++){ v.xx=u.xx+dir[i][0]; v.yy=u.yy+dir[i][1]; v.zz=u.zz+dir[i][2]; if(bianjie(v.xx,v.yy,v.zz)==1){ mark[v.zz][v.xx][v.yy]=1;v.step=u.step+1; q.push(v); } } } } int main() { int i,j,k; char s1[20],s2[20]; while(scanf("%s %d",s1,&n)!=EOF){ getchar(); for(i=0;i<n;i++){ for(j=0;j<n;j++){ for(k=0;k<n;k++) scanf("%c",&mapp[i][j][k]); getchar(); } } scanf("%d %d %d",&sx,&sy,&sz); scanf("%d %d %d",&ex,&ey,&ez); getchar(); gets(s2); if(n==1&&sz==ez&&sx==ex&&sy==ey){ printf("1 0\n"); continue; } memset(mark,0,sizeof(mark)); ff=0; bfs(sx,sy,sz); if(ff==0) printf("NO ROUTE\n"); } return 0; }
