[ACM训练] 算法初级 之 搜索算法 之 深度优先算法DFS (POJ 2251+2488+3083+3009+1321)
2024-03-12 09:23:01
对于深度优先算法，第一个直观的想法是只要是要求输出最短情况的详细步骤的题目基本上都要使用深度优先来解决。比较常见的题目类型比如寻路等，可以结合相关的经典算法进行分析。
常用步骤：
第一道题目：Dungeon Master http://poj.org/problem?id=2251
Input
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5
S....
.###.
.##..
###.# #####
#####
##.##
##... #####
#####
#.###
####E 1 3 3
S##
#E#
### 0 0 0
此题目只要求了求出最短的路径步骤，肯定适合使用广度优先算法来处理，但是如果再要求输出对应最短路径下的具体路径，则只能使用深度优先来处理了。
先来一个广度优先算法的参考代码：
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring> using namespace std; int l,r,c; struct node
{
int i;
int j;
int k;
int s;
}; string road[][];
int visited[**];//i*r*c+j*c+k为索引值 void getroad(int es)
{
int i,j,k;
node first,next;
bool flag=false; for(i=;i<l;i++)
{
for(j=;j<r;j++)
{
for(k=;k<c;k++)
{
if(road[i][j][k] == 'S')//找到初始点，标记
{
first.i=i;
first.j=j;
first.k=k;
first.s=;
flag=true;
break;
}
}
if(flag)
break;
}
if(flag)
break;
} queue<node> q;
q.push(first);
visited[first.i*r*c+first.j*c+first.k]=es; while(!q.empty())
{
first=q.front();
q.pop(); //需要设计上下左右前后6个方向，1维只有上下j左右k，2维以上再添加前后i
//同时需要考虑是否处在边界的情况
next=first;
next.s+=;
int index=; next.j-=;//上
index=next.i*r*c+next.j*c+next.k;
if(next.j>= && road[next.i][next.j][next.k] == '.')
{
if(visited[index] != es)
{
q.push(next);
visited[index]=es;
}
}
if(next.j>= && road[next.i][next.j][next.k] == 'E')
{
cout<<"Escaped in "<<next.s<<" minute(s)."<<endl;
return;
} next.j+=;//下
index=next.i*r*c+next.j*c+next.k;
//cout<<str[next.i][next.j][next.k]<<endl;
if(next.j<r && road[next.i][next.j][next.k] == '.')
{
if(visited[index] != es)
{
q.push(next);
visited[index]=es;
}
}
if(next.j<r && road[next.i][next.j][next.k] == 'E')
{
cout<<"Escaped in "<<next.s<<" minute(s)."<<endl;
return;
} next.j-=;//复原 next.k-=;//左
index=next.i*r*c+next.j*c+next.k;
if(next.k>= && road[next.i][next.j][next.k] == '.')
{
if(visited[index] != es)
{
q.push(next);
visited[index]=es;
}
}
if(next.k>= && road[next.i][next.j][next.k] == 'E')
{
cout<<"Escaped in "<<next.s<<" minute(s)."<<endl;
return;
} next.k+=;//右
index=next.i*r*c+next.j*c+next.k;
if(next.k<c && road[next.i][next.j][next.k] == '.')
{
if(visited[index] != es)
{
q.push(next);
visited[index]=es;
}
}
if(next.k<c && road[next.i][next.j][next.k] == 'E')
{
cout<<"Escaped in "<<next.s<<" minute(s)."<<endl;
return;
} next.k-=;//复原 if(l>)
{
next.i-=;//前
index=next.i*r*c+next.j*c+next.k;
if(next.i>= && road[next.i][next.j][next.k] == '.')
{
if(visited[index] != es)
{
q.push(next);
visited[index]=es;
}
}
if(next.i>= && road[next.i][next.j][next.k] == 'E')
{
cout<<"Escaped in "<<next.s<<" minute(s)."<<endl;
return;
} next.i+=;//后
index=next.i*r*c+next.j*c+next.k;
if(next.i<l && road[next.i][next.j][next.k] == '.')
{
if(visited[index] != es)
{
q.push(next);
visited[index]=es;
}
}
if(next.i<l && road[next.i][next.j][next.k] == 'E')
{
cout<<"Escaped in "<<next.s<<" minute(s)."<<endl;
return;
}
}
}
cout<<"Trapped!"<<endl;
} int main()
{
int count=; while(true)
{
cin>>l>>r>>c; if(l== && r== && c==)
break; int i=;
int j=;
string tmp;
for(i=;i<l;i++)
{
for(j=;j<r;j++)
cin>>road[i][j];
getline(cin,tmp);
}
getroad(count); for(i=;i<l;i++)
for(j=;j<r;j++)
road[i][j].clear(); count++;
} return ;
}
题目更改一下，要求输出最短步数，并且输出对应的具体路径。
考虑一下：
最新文章
- 从零自学Hadoop(06)：集群搭建
- File相关的读取和写入以及复制
- HTML 链接 - href
- 【Django】Django web项目部署（Nginx+uwsgi）
- 内容分发网络CDN（互联网技术）
- Session与Cookie
- 关于server的一些小记
- （原创）monitor Dell Powerconnec 6224 with cacti
- mysql 数据库还原出错ERROR:Unknown command '\' mysql中断
- C#中如何使用IComparable<T>与IComparer<T>接口（转载）
- Spark2.1集群安装（standalone模式）
- 【BZOJ4556】字符串（后缀数组，主席树）
- 3. Linux系统磁盘分区介绍
- Git安装以及常用命令(图文详解)
- AIX使用命令修改网卡IP地址，永久生效
- Python 学习笔记1 安装和IDE
- Django获取数据库数据时根据id筛选
- Cracking The Coding Interview 2.5
- Struts2 调用非execute方法
- DirectX中文手册