公司主页网站开发,综合权重查询,设计学校网站模板免费下载,视频不可添加橱窗入口解题思路
用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出.
代码
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#in…
解题思路
用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出.
代码
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
using namespace std;
int g[120][120];
struct s
{int x;int y;
}d[120*120];
int l,r;
struct ss
{int x;int y;int z;
}j[120][120];
int a,b,c;
int k,i;
int bfs()
{int tx,ty,z;while(lr){for(z0;z6;z){txd[l].x;tyd[l].y;switch(z){case 0:txa;break;case 1:tyb;break;case 2:tx0;break;case 3:ty0;break;case 4:if(tx!0){if(txtyb){tytxty;tx0;}else{txtx-(b-ty);tyb;}}break;case 5:if(ty!0){if(txtya){txtytx;ty0;}else{tyty-(a-tx);txa;}}break;}if(txa||tyb||tx0||ty0)continue;if(txc||tyc){ktx;ity;j[k][i].xd[l].x;j[k][i].yd[l].y;j[k][i].zz;g[tx][ty]g[d[l].x][d[l].y]1;return 0;}if(g[tx][ty]-1){g[tx][ty]g[d[l].x][d[l].y]1;d[r].xtx;d[r].yty;j[tx][ty].xd[l].x;j[tx][ty].yd[l].y;j[tx][ty].zz;}}l;}return 0;
}void print(int x,int y)
{if(x0y0)return ;print(j[x][y].x,j[x][y].y);switch(j[x][y].z){case 0:printf(FILL(1)\n);break;case 1:printf(FILL(2)\n);break;case 2:printf(DROP(1)\n);break;case 3:printf(DROP(2)\n);break;case 4:printf(POUR(1,2)\n);break;case 5:printf(POUR(2,1)\n);break;}return ;
}int main()
{scanf(%d%d%d,a,b,c);d[r].x0;d[r].y0;memset(g,-1,sizeof(int )*120*120);g[0][0]0;bfs();if(k0i0){printf(impossible\n);}else{printf(%d\n,g[k][i]);print(k,i);}return 0;
}解题思路
这道题用bfs就行了.以两个人为起点对全图进行搜索,用一个数组保存到每一个地方所用的最短的步数.最后比较两人到所有的kfc所用的步数的总和输出最小的就行了.
代码
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
using namespace std;
char g[210][210];
int j[210][210];
int j2[210][210];
int ne[5][2]{{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
struct di
{int x;int y;
}sy,sm,kfc[210*210],dl[210*210];
int l,r;
int k;
int sum;int bfs()
{int tx,ty,z;while(lr){for(z0;z4;z){txne[z][0]dl[l].x;tyne[z][1]dl[l].y;if(tx0||txn||ty0||tym)continue;if(g[tx][ty]!#j[tx][ty]0){j[tx][ty]j[dl[l].x][dl[l].y]1;dl[r].xtx;dl[r].yty;}}l;}return 0;
}int bfs2()
{int tx,ty,z;while(lr){for(z0;z4;z){txne[z][0]dl[l].x;tyne[z][1]dl[l].y;if(tx0||txn||ty0||tym)continue;if(g[tx][ty]!#j2[tx][ty]0){j2[tx][ty]j2[dl[l].x][dl[l].y]1;dl[r].xtx;dl[r].yty;}}l;}return 0;
}int main()
{int x,y,s;while(~scanf(%d%d,n,m)){sum9999999;k0;for(x0;xn;x){scanf(%s,g[x]);}for(x0;xn;x){for(y0;ym;y){if(g[x][y]Y){sy.xx;sy.yy;}if(g[x][y]M){sm.xx;sm.yy;}if(g[x][y]){kfc[k].xx;kfc[k].yy;}}}memset(j,0,sizeof(int)*210*210);l0;r0;dl[r].xsy.x;dl[r].ysy.y;bfs();memset(j2,0,sizeof(int)*210*210);l0;r0;dl[r].xsm.x;dl[r].ysm.y;bfs2();for(x0;xk;x){if(j[kfc[x].x][kfc[x].y]!0j2[kfc[x].x][kfc[x].y]!0)if((j[kfc[x].x][kfc[x].y]j2[kfc[x].x][kfc[x].y])sum)sumj[kfc[x].x][kfc[x].y]j2[kfc[x].x][kfc[x].y];}printf(%d\n,sum*11);}return 0;
}解题思路
用bfs搜索,要注意的是地图是三维的,传送到下一层之后可能的情况(直接见到公主,撞死,进入另一个传送门).
代码
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
using namespace std;
char g[3][15][15];
int j[3][15][15];
struct ss
{int x;int y;int z;
}d[15*15*3];
int ne[5][2]{{1,0},{-1,0},{0,1},{0,-1}};
int l,r;
int n,m,t;
int bfs()
{int z,tx,ty,tz;while(lr){for(int z0;z4;z){txd[l].xne[z][0];tyd[l].yne[z][1];tzd[l].z;if(tx0||ty0||txn||tym)continue;if(g[tz][tx][ty]P){return j[tz][tx][ty]j[d[l].z][d[l].x][d[l].y]1;}if(g[tz][tx][ty]!*j[tz][tx][ty]-1){j[tz][tx][ty]j[d[l].z][d[l].x][d[l].y]1;if(g[tz][tx][ty]#){if(tz0){tz;}else{tz--;}if(g[tz][tx][ty]#||j[tz][tx][ty]!-1){if(tz0){tz;}else{tz--;}continue;}if(g[tz][tx][ty]*||j[tz][tx][ty]!-1){if(tz0){tz;}else{tz--;}continue;}if(g[tz][tx][ty]P){return j[tz][tx][ty]j[d[l].z][d[l].x][d[l].y]1;}j[tz][tx][ty]j[d[l].z][d[l].x][d[l].y]1;}d[r].xtx;d[r].yty;d[r].ztz;}}l;}return 999999;
}
int main()
{int k;scanf(%d,k);for(int z0;zk;z){memset(j,-1,sizeof(int )*3*15*15);lr0;scanf(%d%d%d,n,m,t);for(int x0;xn;x){scanf(%s,g[0][x]);}getchar();for(int x0;xn;x){scanf(%s,g[1][x]);}d[r].x0;d[r].y0;d[r].z0;j[0][0][0]0;int sumbfs();if(sumt){printf(YES\n);}else{printf(NO\n);}}return 0;
}
