外贸谷歌网站推广网站子页面设计

外贸谷歌网站推广,网站子页面设计,淘宝客怎么样做网站,网站规划建设书前几篇都讲了关于搜索的内容#xff0c;现在就来做做习题吧#xff01;#xff01;#xff01; #xff08;没看以前我的文章的人请看专栏#xff1a;https://blog.csdn.net/mayuteng1/category_13083478.html?spm1001.2014.3001.5482#xff09; 注#xff1a;名字…前几篇都讲了关于搜索的内容现在就来做做习题吧没看以前我的文章的人请看专栏https://blog.csdn.net/mayuteng1/category_13083478.html?spm1001.2014.3001.5482注名字别管其实就是Robin题目描述这天 SB Robin 正打着游戏正思考着怎么才能过关突然bong 的一声家里的水管全爆了已知 SB Robin 的家可以用一个 n*m 的网格表示。SB Robin 每秒钟可以走到上下左右 4 个方向的相邻格中的一个没有水的格子他不喜欢踩水而所有有水的格子每秒也会向四周的空格蔓延上下左右四个格子。显然最开始有水的格子是那些水管的位置。SB Robin 家还有一些障碍格比如他家的 60 英寸的大电视比如一些紫檀木家具还有墙也是一种障碍……水跟 SB Robin 都不能进入这个格。当他到达地图边界时就可以认为他逃出了他家。请问SB Robin 怎么以最短的时间逃出家。 注意1.等 SB Robin 反应过来时已经过去了1秒。2.开始时水可能不止一处。输入格式第一行两个整数 n 和 m表示 SB Robin 家的行数跟列数。接下来是一个 n*m 的字符串矩阵。其中.表示空地水和 SB Robin 都能进去s表示 SB Robin 所在位置w表示爆掉的水管的位置#表示障碍和墙 水和 SB Robin 都不能进去。输出格输入数据仅一行能逃出去则输出一个整数表示 SB Robin 逃出家的最短时间。如果 SB Robin 出不去则输出IMPOSSIBLE(不含引号)。输入输出样例输入数据 14 4 #### #sw# #..# #..#输出数据 13输入数据 23 4 #### #s.# #.w.输出数据 2IMPOSSIBLE数据范围与约定对于20%的数据1n,m100对于100%的数据1n,m1000。正在看我的博客的人在这里其实可以自己先试着打一下代码————————我是分割线——————————这题一眼搜索啊不过这题用DFS的话肯定会超时的而且其实我这道题连DFS该怎么打都不知道……所以这道题我们只能用广度优先搜索BFS来做代码如下精髓都在注释中#includebits/stdc.h using namespace std; long long n,m;//n,m表示矩阵的长和宽 long long a[1005][1005],xx,yy;//a数组用来判断这个地方是否是墙,xx/yy分别表示Robin的坐标 long long minnINT_MAX;//minn表示Robin到边缘的最短距离 long long dx[]{-1,1,0,0},dy[]{0,0,-1,1};//方向数组 long long b[1005][1005],c[1005][1005];//b数组表示水流到这个地方的最短距离c数组表示Robin到这个地方的最短距离 queuepairint,int q;//队列用来打BFS void bfs1()//第一个BFS用来枚举水 { while(!q.empty()) { int xq.front().first,yq.front().second;//获取x和y坐标 q.pop();//弹出 for(int i0;i4;i)//枚举四个方向 { int nxxdx[i],nyydy[i]; if(nx1ny1nxnnymb[nx][ny]0a[nx][ny]!-1) { //当x和y坐标在规定范围内且这个地方没有来过且这个地方不是墙则加入队列 b[nx][ny]b[x][y]1;//标记这个地方的步数比原来的地方的步数多一 q.push({nx,ny}); } } } } void bfs2()//第二个BFS用来枚举Robin { q.push({xx,yy});//加入Robin的x和y坐标 while(!q.empty()) { int xq.front().first,yq.front().second; q.pop(); for(int i0;i4;i) { int nxxdx[i],nyydy[i]; if(nx1ny1nxnnymc[nx][ny]INT_MAX-1a[nx][ny]!-1b[nx][ny]1c[x][y]) { //多了一个条件那就是水流到这一格的最小步数要比Robin到这一格的最小步数多1 c[nx][ny]c[x][y]1;//累计 q.push({nx,ny});//加入新的x和y坐标 } } } } int main(){ cinnm; for(int i1;in;i) { char ch; for(int j1;jm;j) { cinch; if(ch#)a[i][j]-1,c[i][j]INT_MAX;//如果是墙则a[i][j]-1,c[i][j]也要标记 else if(chs)xxi,yyj,a[i][j]1,c[i][j]0;//获取Robin的坐标 else if(chw)q.push({i,j}),a[i][j]2,c[i][j]INT_MAX;//由于可能有多处水管爆裂所以在这里就要入队了 else c[i][j]INT_MAX-1;//空地的话c[i][j]INT_MAX-1 } } bfs1();//第一个BFS bfs2();//第二个BFS //枚举矩阵的四周假如Robin到这一格的时间比水到这一格的时间短则minnmin(minn,Robin到这一格的时间) for(int i1;in;i) { if(b[i][1]c[i][1])minnmin(minn,c[i][1]); if(b[i][m]c[i][m])minnmin(minn,c[i][m]); } for(int i1;im;i) { if(b[1][i]c[1][i])minnmin(minn,c[1][i]); if(b[n][i]c[n][i])minnmin(minn,c[n][i]); } if(minnINT_MAX)coutIMPOSSIBLE;//加入minn没有更新最小值则Robin逃离不了了 else coutminn1;//否则输出minn1 return 0; }