电子老鼠闯迷宫
#include<iostream> #include<queue> using namespace std; char map[15][15]; int sx,sy,ex,ey; int INF=500; int d[15][15]; int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; struct point{ int x; int y; point(int x,int y):x(x),y(y){} }; queue<point> q; int bfs(); int main(){ cin>>sx>>sy>>ex>>ey; for(int i=1;i<=12;i++){ for(int j=1;j<=12;j++){ cin>>map[i][j]; d[i][j]=INF; } } d[sx][sy]=0; q.push(point(sx,sy)); cout<<bfs()<<endl; return 0; } int bfs(){ while(!q.empty()){ point p=q.front(); q.pop(); int nx=p.x,ny=p.y; if(nx==ex&&ny==ey)break; for(int i=0;i<4;i++){ int tx=nx+dx[i],ty=ny+dy[i]; if(tx>0&&tx<=12 &&ty>0&&ty<=12 &&map[tx][ty]!='X' &&d[tx][ty]==500){ q.push(point(tx,ty)); d[tx][ty]=d[nx][ny]+1; } } } return d[ex][ey]; }跳马
#include<iostream> #include<queue> #include<cmath> #include<cstring> using namespace std; int dx[8]={1,2,2,1,-1,-2,-2,-1}; int dy[8]={-2,-1,1,2,2,1,-1,-2}; int derta=3; int n; int sx,sy,ex,ey; int bushu[210][210];//步数很大（0x3f）的话，就是还没有到达过 struct point{ int x; int y; int step; point(int x=0,int y=0,int step=0):x(x),y(y),step(step){} /*bool operator < (const point &b) { int dis=abs(x-ex)+abs(y-ey)+derta*step; int disb=abs(b.x-ex)+abs(b.y-ey)+derta*b.step; return dis<disb; }*/ }; bool operator<(point a,point b){ int disa=abs(a.x-ex)+abs(a.y-ey)+derta*a.step; int disb=abs(b.x-ex)+abs(b.y-ey)+derta*b.step; return disa>disb; } priority_queue<point> q; int bfs(); int main(){ cin>>n; for(int i=0;i<n;i++){ memset(bushu,0x3f,sizeof(bushu)); while(!q.empty())q.pop(); cin>>sx>>sy>>ex>>ey; q.push(point(sx,sy,0)); bushu[sx][sy]=0; cout<<bfs()<<endl; } return 0; } int bfs(){ while(!q.empty()){ point p=q.top(); q.pop(); int nx=p.x,ny=p.y,nstep=p.step; if(nx==ex&&ny==ey)break; for(int i=0;i<8;i++){ int tx=nx+dx[i],ty=ny+dy[i],tstep=nstep+1; if(tx>0&&tx<=200 &&ty>0&&ty<=200 &&bushu[tx][ty]==0x3f3f3f3f){ q.push(point(tx,ty,tstep)); bushu[tx][ty]=tstep; } } } return bushu[ex][ey]; }独轮车
#include<iostream> #include<cstring> #include<queue> #include<map> using namespace std; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; char Map[25][25]; int bushu[25][25][10][10];//x坐标，y坐标，颜色，方向 int sx,sy,sc,sd;char ch_sc,ch_sd; int ex,ey,ec;char ch_ec; struct state{ int x; int y; int col; int dir; state(int x,int y,int col,int dir):x(x),y(y),col(col),dir(dir){} }; queue<state> q; int bfs(); int main(){ map<char,int> mc,md; //颜色 mc['R']=0;mc['Y']=1;mc['B']=2;mc['W']=3;mc['G']=4; //方向 md['E']=0;md['S']=1;md['W']=2;md['N']=3; memset(bushu,0x3f,sizeof(bushu)); cin>>sx>>sy>>ch_sc>>ch_sd; cin>>ex>>ey>>ch_ec; for(int i=1;i<=20;i++){ for(int j=1;j<=20;j++){ cin>>Map[i][j]; } } //将字符信息转换为数字信息表示颜色和方向 sc=mc[ch_sc]; sd=md[ch_sd]; ec=mc[ch_ec]; q.push(state(sx,sy,sc,sd)); bushu[sx][sy][sc][sd]=0; cout<<bfs()<<endl; return 0; } int bfs(){ int ans=0x3f3f3f3f;//0x3f3f3f3f表示无解 while(!q.empty()){ state s=q.front(); q.pop(); int nx=s.x,ny=s.y,nc=s.col,nd=s.dir; if(nx==ex&&ny==ey&&nc==ec){ ans=bushu[nx][ny][nc][nd]; break; } int tx,ty,tc,td; //一共有3种变化：向前走，向左转一下，向右转一下 //向前走 tx=nx+dx[nd]; ty=ny+dy[nd]; tc=(nc+1)%5; td=nd; if(tx>=1&&tx<=20 &&ty>=1&&ty<=20 &&Map[tx][ty]!='X' &&bushu[tx][ty][tc][td]==0x3f3f3f3f){ q.push(state(tx,ty,tc,td)); bushu[tx][ty][tc][td]=bushu[nx][ny][nc][nd]+1; } //左转 tx=nx; ty=ny; tc=nc; td=(nd+1)%4; if(bushu[tx][ty][tc][td]==0x3f3f3f3f){ q.push(state(tx,ty,tc,td)); bushu[tx][ty][tc][td]=bushu[nx][ny][nc][nd]+1; } //右转 tx=nx; ty=ny; tc=nc; td=(nd+3)%4; if(bushu[tx][ty][tc][td]==0x3f3f3f3f){ q.push(state(tx,ty,tc,td)); bushu[tx][ty][tc][td]=bushu[nx][ny][nc][nd]+1; } } return ans; }六数码问题
#include<iostream> #include<queue> #include<cstring> using namespace std; int visited[7][7][7][7][7][7];//为0则没有访问过 int s[6],e[6]={1,2,3,4,5,6}; struct state{ int ar[6]; state(int a[6]){ for(int i=0;i<6;i++){ ar[i]=a[i]; } } }; queue<state> q; void swap_ar_a(int a[]){ int t=a[0]; a[0]=a[3]; a[3]=a[4]; a[4]=a[1]; a[1]=t; } void swap_ar_b(int a[]){ int t=a[1]; a[1]=a[4]; a[4]=a[5]; a[5]=a[2]; a[2]=t; } bool bfs(); int main(){ while(cin>>s[0]){ for(int i=1;i<6;i++)cin>>s[i]; //先初始化 memset(visited,0,sizeof(visited)); while(!q.empty())q.pop(); q.push(state(s)); visited[s[0]][s[1]][s[2]][s[3]][s[4]][s[5]]=1; if(bfs()){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } return 0; } bool bfs(){ while(!q.empty()){ state s=q.front(); q.pop(); int ns[6]; int flag=1;//判断是否到达目标状态 for(int i=0;i<6;i++){ ns[i]=s.ar[i]; if(ns[i]!=e[i])flag=0; } if(flag)return true; //考察两种变换 //a变换 swap_ar_a(ns); if(visited[ns[0]][ns[1]][ns[2]][ns[3]][ns[4]][ns[5]]==0){ q.push(state(ns)); visited[ns[0]][ns[1]][ns[2]][ns[3]][ns[4]][ns[5]]=1; } swap_ar_a(ns);swap_ar_a(ns);swap_ar_a(ns); //b变换 swap_ar_b(ns); if(visited[ns[0]][ns[1]][ns[2]][ns[3]][ns[4]][ns[5]]==0){ q.push(state(ns)); visited[ns[0]][ns[1]][ns[2]][ns[3]][ns[4]][ns[5]]=1; } swap_ar_b(ns);swap_ar_b(ns);swap_ar_b(ns); } return false; }加1乘2平方
#include<iostream> #include<queue> using namespace std; int s,e; int visited[10010]; struct state{ int num; int step; state(int num,int step):num(num),step(step){} }; queue<state> q; int bfs(); int main(){ cin>>s>>e; visited[s]=1; q.push(state(s,0)); cout<<bfs()<<endl; return 0; } int bfs(){ while(!q.empty()){ state ns=q.front(); int n=ns.num,nstep=ns.step; q.pop(); if(n==e)return nstep; if(n+1<=e&&visited[n+1]==0){ visited[n+1]=1; q.push(state(n+1,nstep+1)); } if(n*2<=e&&visited[n*2]==0){ visited[n*2]=1; q.push(state(n*2,nstep+1)); } if(n*n<=e&&visited[n*n]==0){ visited[n*n]=1; q.push(state(n*n,nstep+1)); } } }找倍数
#include<iostream> #include<string> #include<queue> using namespace std; string ans="1"; int n; queue<string> q; bool is_ok(string s,int n); string bfs(); int main(){ cin>>n; while(n!=0){ ans="1"; while(!q.empty())q.pop(); q.push(ans); cout<<bfs()<<endl; cin>>n; } return 0; } string bfs(){ while(!q.empty()){ string s=q.front(); //cout<<s<<endl; q.pop(); if(!(n%2==0&&s[s.size()-1]=='1') &&is_ok(s,n))return s; else if(is_ok(s,n))return s; string s1=s+'0'; q.push(s1); string s2=s+'1'; q.push(s2); } } bool is_ok(string s,int n){ int sum=0; int size=s.size(); for(int i=0;i<size;i++){ sum*=10; sum+=s[i]-'0'; sum%=n; } if(sum==0)return true; else return false; }木乃伊迷宫
#include<iostream> #include<queue> using namespace std; int n; int dx,dy,dtype; int msx,msy;//木乃伊 int rsx,rsy;//人 int ex,ey;//出口 int visited[6][6][6][6]; int Dx[4]={0,1,0,-1}; int Dy[4]={-1,0,1,0}; struct point{ int door[4]; point(int a=0,int b=0,int c=0,int d=0){ door[0]=a;door[1]=b;door[2]=c;door[3]=d; } }; point map[6][6]; struct state{ int mx,my; int rx,ry; state(int a,int b,int c,int d):mx(a),my(b),rx(c),ry(d){} }; queue<state> q; bool bfs(); int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>dx>>dy>>dtype; if(dtype==0){ map[dx][dy].door[1]=1; if(dx+1<6)map[dx+1][dy].door[3]=1; } else if(dtype==1){ map[dx][dy].door[2]=1; if(dx+1<6)map[dx][dy+1].door[0]=1; } } cin>>msx>>msy>>rsx>>rsy>>ex>>ey; q.push(state(msx,msy,rsx,rsy)); visited[msx][msy][rsx][rsy]=1; if(bfs()){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } return 0; } bool bfs(){ while(!q.empty()){ state s=q.front(); q.pop(); int mnx=s.mx,mny=s.my,rnx=s.rx,rny=s.ry; //cout<<mnx<<' '<<mny<<' '<<rnx<<' '<<rny<<endl; if(rnx==ex&&rny==ey)return true; //人的一步 for(int i=0;i<4;i++){ if(mny==rny&&mnx==rnx)continue; int rtx=rnx+Dx[i],rty=rny+Dy[i]; int flag=1;//表示该状态可行 if(!(rtx>=0&&rtx<6 &&rty>=0&&rty<6 &&map[rnx][rny].door[i]==0))continue; if(mny==rty&&mnx==rtx)continue; //木乃伊的两步 mnx=s.mx,mny=s.my; for(int j=0;j<2;j++){ if(rty==mny){//同一列 if(rtx<mnx)//人在上面 { if(map[mnx][mny].door[3]==0)mnx--; } else if(rtx>mnx)//人在下面 { if(map[mnx][mny].door[1]==0)mnx++; } } else if(rty<mny){//木乃伊需要往左移动 if(map[mnx][mny].door[0]==0)mny--; } else if(rty<mny){//木乃伊需要向右移动 if(map[mnx][mny].door[2]==0)mny++; } //考察这一步走后是否木乃伊会碰到人 if(mny==rty&&mnx==rtx){ flag=0; break; } } if(flag==0)continue;//不可行的状态，就要考察其他状态 //木乃伊走完，考察状态 if(visited[mnx][mny][rtx][rty]==0){ visited[mnx][mny][rtx][rty]=1; q.push(state(mnx,mny,rtx,rty)); } } } return false; }polygon
#include<iostream> #include<cmath> #include<iomanip> using namespace std; int n,m; double nxy[1010]; double ans=0; int main(){ cin>>n>>m; //一共有n+m个坐标 //求出n个点每一个的坐标 for(int i=1;i<=n;i++){ nxy[i]=(n+m)/double(n)*i; } //统计所有坐标到最近位置的距离 for(int i=1;i<=n;i++){ ans+=min( ceil(nxy[i])-nxy[i] , nxy[i]-floor(nxy[i]) ); } //换算成标准距离，输出 cout<<fixed<<setprecision(4)<<ans*10000.0/(n+m)<<endl; return 0; }推箱子
#include<iostream> #include<queue> #include<cmath> #include<string> using namespace std; int map[20][20]; string s[11]; int ex,ey; int rsx,rsy; int bsx,bsy; int visited[11][11][11][11]; struct state{ int rx,ry; int bx,by; int step; state(int a,int b,int c,int d,int e):rx(a),ry(b),bx(c),by(d),step(e){} }; queue<state> q; int bfs(); int main(){ for(int i=0;i<10;i++)cin>>s[i]; for(int i=1;i<=10;i++){ for(int j=1;j<=10;j++){ map[i][j]=(s[i-1][j-1]-'0'); if(map[i][j]==2){ bsx=i; bsy=j; } else if(map[i][j]==3){ ex=i; ey=j; } else if(map[i][j]==4){ rsx=i; rsy=j; } } } q.push(state(rsx,rsy,bsx,bsy,0)); visited[rsx][rsy][bsx][bsy]=1; cout<<bfs()<<endl; return 0; } int bfs(){ while(!q.empty()){ state s=q.front(); int rnx=s.rx,rny=s.ry,bnx=s.bx,bny=s.by,nstep=s.step; //cout<<rnx<<' '<<rny<<' '<<bnx<<' '<<bny<<' '<<nstep<<endl; q.pop(); if(bnx==ex&&bny==ey)return nstep; //一下枚举所有移动 //人和箱子靠在一起且可以往另一边移动 if(rnx==bnx&&rny+1==bny&&rny+2<=10&&visited[rnx][rny+1][rnx][rny+2]==0&&map[rnx][rny+2]!=1){ q.push(state(rnx,rny+1,rnx,rny+2,nstep+1)); visited[rnx][rny+1][rnx][rny+2]=1; } if(rnx==bnx&&rny-1==bny&&rny-2>=1&&visited[rnx][rny-1][rnx][rny-2]==0&&map[rnx][rny-2]!=1){ q.push(state(rnx,rny-1,rnx,rny-2,nstep+1)); visited[rnx][rny-1][rnx][rny-2]=1; } if(rny==bny&&rnx+1==bnx&&rnx+2<=10&&visited[rnx+1][rny][rnx+2][rny]==0&&map[rnx+2][rny]!=1){ q.push(state(rnx+1,rny,rnx+2,rny,nstep+1)); visited[rnx+1][rny][rnx+2][rny]=1; } if(rny==bny&&rnx-1==bnx&&rnx-2>=1&&visited[rnx-1][rny][rnx-2][rny]==0&&map[rnx-2][rny]!=1){ q.push(state(rnx-1,rny,rnx-2,rny,nstep+1)); visited[rnx-1][rny][rnx-2][rny]=1; } //接下来就是人不推箱子，只是走一走的过程 //按照左下右上顺序 //注意人不能穿过箱子 if(rny-1>=1&&visited[rnx][rny-1][bnx][bny]==0&&map[rnx][rny-1]!=1&&!(rnx-bnx==0&&rny-1-bny==0)){ q.push(state(rnx,rny-1,bnx,bny,nstep+1)); visited[rnx][rny-1][bnx][bny]=1; } if(rnx+1<=10&&visited[rnx+1][rny][bnx][bny]==0&&map[rnx+1][rny]!=1&&!(rnx+1-bnx==0&&rny-bny==0)){ q.push(state(rnx+1,rny,bnx,bny,nstep+1)); visited[rnx+1][rny][bnx][bny]=1; } if(rny+1<=10&&visited[rnx][rny+1][bnx][bny]==0&&map[rnx][rny+1]!=1&&!(rnx-bnx==0&&rny+1-bny==0)){ q.push(state(rnx,rny+1,bnx,bny,nstep+1)); visited[rnx][rny+1][bnx][bny]=1; } if(rnx-1>=1&&visited[rnx-1][rny][bnx][bny]==0&&map[rnx-1][rny]!=1&&!(rnx-1-bnx==0&&rny-bny==0)){ q.push(state(rnx-1,rny,bnx,bny,nstep+1)); visited[rnx-1][rny][bnx][bny]=1; } } return -1; }特殊的二阶魔方
#include<iostream> #include<map> #include<queue> using namespace std; int t[2]; char s[6][4]; int v[16][16][16][16][16][16]; struct state{ char f[6][4]; int num[6]; int step; state(char ch[6][4],int s){ for(int i=0;i<6;i++){ num[i]=0; for(int j=0;j<4;j++){ f[i][j]=ch[i][j]; num[i]*=2; num[i]+=ch[i][j]-'0'; } } step=s; } }; queue<state> q; void visited(state s){ int a=s.num[0],b=s.num[1],c=s.num[2],d=s.num[3],e=s.num[4],f=s.num[5]; v[a][b][c][d][e][f]=1; } bool isnt_visited(state s){ int a=s.num[0],b=s.num[1],c=s.num[2],d=s.num[3],e=s.num[4],f=s.num[5]; if(v[a][b][c][d][e][f]==0)return true; else return false; } void fengzhuang(char c[6][4],int step){ state t(c,step+1); if(isnt_visited(t)){ visited(t); q.push(t); } } void sw(char c[6][4],int ai,int aj,int bi,int bj,int ci,int cj,int di,int dj){ int t=c[ai][aj]; c[ai][aj]=c[di][dj]; c[di][dj]=c[ci][cj]; c[ci][cj]=c[bi][bj]; c[bi][bj]=t; } void b1(char c[6][4]); void b2(char c[6][4]); void b3(char c[6][4]); int bfs(); int main(){ for(int i=0;i<6;i++){ for(int j=0;j<2;j++){ cin>>t[j]; } s[i][0]=t[0]/10+'0'; s[i][1]=t[0]+'0'; s[i][2]=t[1]/10+'0'; s[i][3]=t[1]+'0'; } /*for(int i=0;i<6;i++){ for(int j=0;j<4;j++){ cout<<s[i][j]; } cout<<endl; }*/ state st(s,0); visited(st); q.push(st); cout<<bfs()<<endl; return 0; } void b1(char c[6][4]){ sw(c,2,2,5,3,3,3,4,2); sw(c,2,3,5,2,3,2,4,3); sw(c,1,2,1,0,1,1,1,3); } void b2(char c[6][4]){ sw(c,1,3,4,1,0,1,5,3); sw(c,1,1,4,3,0,3,5,1); sw(c,3,0,3,2,3,3,3,1); } void b3(char c[6][4]){ sw(c,2,0,0,1,3,2,1,0); sw(c,2,2,0,0,3,0,1,1); sw(c,5,2,5,0,5,1,5,3); } int bfs(){ while(!q.empty()){ state n=q.front(); q.pop(); char fn[6][4]; int nstep=n.step; for(int i=0;i<6;i++){ int flag=1; for(int j=0;j<4;j++){ fn[i][j]=n.f[i][j]; if(fn[i][j]!='0')flag=0; } if(flag)return nstep; } /*for(int i=0;i<6;i++){ for(int j=0;j<4;j++){ cout<<fn[i][j]; } cout<<endl; }*/ //1：得到变换之后的字符串数组 //2：得到状态 //3：判断状态是否重复 //4：没有重复则加入队列 //5：2~4都封装到fengzhuang函数里面进行 //1 b1(fn); fengzhuang(fn,nstep); //2 b1(fn);b1(fn); fengzhuang(fn,nstep); b1(fn); //3 b2(fn); fengzhuang(fn,nstep); //4 b2(fn);b2(fn); fengzhuang(fn,nstep); b2(fn); //5 b3(fn); fengzhuang(fn,nstep); //6 b3(fn);b3(fn); fengzhuang(fn,nstep); b3(fn); } return -1; }
