目录
1.Dungeon Master
2.Oil Deposits
3.Find a way
1.Dungeon Master
Sample
| Inputcopy | Outputcopy |
|---|---|
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0 | Escaped in 11 minute(s). Trapped! |
这道题与普通的bfs模板题就是地图变成三维的了，其余一律按照模板做法来即可。
下面是AC代码：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int h,n,m;
char mp[35][35][35];
struct point{//结构体定义
int z,x,y,step;
};
int v[35][35][35];//是否遍历判断数组
int dx[]={1,-1,0,0,0,0};//枚举6个操作
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int main()
{
while(cin>>h>>n>>m){
if(h==0&&n==0&&m==0) break;//运行结束标志
int ex,ey,ez,sx,sy,sz;
for(int i=1;i<=h;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=m;k++){
cin>>mp[i][j][k];
if(mp[i][j][k]=='S')
{
sz=i,sx=j,sy=k;//找到起点位置
}
if(mp[i][j][k]=='E')
{
ez=i,ex=j,ey=k;//找到终点位置
}
}
}
}
queue<point>q;
point st;
st.x=sx,st.y=sy,st.z=sz,st.step=0;
v[sz][sx][sy]=1;
q.push(st);
int f=0;
while(!q.empty()){
point k=q.front();
q.pop();
if(k.x==ex&&k.y==ey&&k.z==ez)//到达位置
{
f=1;
cout<<"Escaped in "<<k.step<<" minute(s).\n";//按照格式输出
break;
}
for(int i=0;i<6;i++){
int tx=k.x+dx[i];
int ty=k.y+dy[i];
int tz=k.z+dz[i];
if(tx<1||ty<1||tz<1||tz>h||tx>n||ty>m||mp[tz][tx][ty]=='#'||v[tz][tx][ty]) continue;//错误位置判断
v[tz][tx][ty]=1;
point p;
p.x=tx,p.y=ty,p.z=tz,p.step=k.step+1;
q.push(p);//赋值入队
}
}
if(f==0)
{
cout<<"Trapped!\n";//走不出
}
memset(v,0,sizeof(v));//初始化，防止对下一次数据造成影响
}
return 0;
}2.Oil Deposits
Sample
| Inputcopy | Outputcopy |
|---|---|
1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0 | 0 1 2 2 |
该题需要我们找出有多少种类的油，当两油的相对位置如下
则这两油为同一种类的油，可以用dfs对一油袋周围深搜，搜到的油改为平底，这用每搜一次，对应的不同种类油就可以+1。
下面是AC代码：
#include<cstdio>
#include<iostream>
using namespace std;
char mp[120][120];
int n,m,ans;
int dx[8]={-1,-1,0,1,1,1,0,-1};//操作方向
int dy[8]={0,1,1,1,0,-1,-1,-1};
void dfs(int x,int y)
{
if(x<0||y<0||x>=n||y>=m) return;//越界停止搜
if(mp[x][y]=='@')
{
mp[x][y]='*';
for(int i=0;i<8;i++){
dfs(x+dx[i],y+dy[i]);//继续搜
}
}
return;
}
int main()
{
while(cin>>n>>m){
if(n==0&&m==0) break;
ans=0;//初始化
for(int i=0;i<n;i++)
cin>>mp[i];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]=='@')//发现不同种类油袋
ans++,dfs(i,j);//将与它连通的油袋变为'*'
}
}
cout<<ans<<"\n";
}
return 0;
}3.Find a way
Sample
| Inputcopy | Outputcopy |
|---|---|
4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...# | 66 88 66 |
这道题要求我们找到一个Y和M去到一家肯德基汇合的最短时间和，我们可以分别给Y和M定义一个距离数组，为Y和M到相应位置的距离，后面对肯德基的位置比较，找到一个最短距离和。
下面是AC代码：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
char mp[201][201];
int v[201][201];
int dis1[201][201],dis2[201][201];//定义两个距离数组
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
struct node{
int x,y;
};
int bfs(int x,int y,int n,int m,char f)
{
queue<node>q;
node st;
int ans=0;
st.x=x,st.y=y;
v[x][y]=1;
q.push(st);
while(!q.empty()){
node k=q.front();
q.pop();
for(int i=0;i<4;i++){
int tx=k.x+dx[i];
int ty=k.y+dy[i];
if(!v[tx][ty]&&mp[tx][ty]!='#'&&tx>=1&&ty>=1&&tx<=n&&ty<=m)
{
v[tx][ty]=1;
node p;
if(f=='Y') dis1[tx][ty]=dis1[k.x][k.y]+1;//按照f，给相应的距离数组赋值
else dis2[tx][ty]=dis2[k.x][k.y]+1;
p.x=tx,p.y=ty;;
q.push(p);
}
}
}
return ans*11;
}
int main()
{
int n,m;
while(cin>>n>>m){
node kfc[40100];
int z=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='@') kfc[++z].x=i,kfc[z].y=j;//找到每家kcf的位置
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='Y')
{
bfs(i,j,n,m,'Y');
memset(v,0,sizeof(v));//初始化
}
if(mp[i][j]=='M')
{
bfs(i,j,n,m,'M');
memset(v,0,sizeof(v));
}
}
}
int ans=1e8;
for(int i=1;i<=z;i++){
if(dis1[kfc[i].x][kfc[i].y]!=0&&dis2[kfc[i].x][kfc[i].y]!=0)
ans=min(ans,dis1[kfc[i].x][kfc[i].y]+dis2[kfc[i].x][kfc[i].y]);//更新最短距离
}
cout<<ans*11<<"\n";
memset(dis1,0,sizeof(dis1));//初始化
memset(dis2,0,sizeof(dis2));
}
return 0;
}
