HDU 1242 dFS 找目标最短路
2024-08-29 23:20:59
//多个起点，要最短得目标，不妨倒过来从目标出发，去找最近的点更新！！！！！！递归时思路要清楚 #include<iostream>
#include<cstring>
using namespace std;
int a[202][202]; int ax,ay;int f[4][2]={0,1,1,0,-1,0,0,-1};int mmin=50000;int visit[202][202];
void dfs(int x,int y,int count)
{
if(a[x][y]==0)return;
else if(a[x][y]==2)count=count+2; //步数计数！不同情况。每次走一步深一层时计数
else count++;
if(a[x][y]==4) //出口！
{
if(count<mmin)mmin=count;
}
else
{
for(int i=0;i<4;i++) //走
{
if(visit[x][y]==0&&a[x][y]!=0) //没访问或者不被限制的
{
visit[x][y]=1;
dfs(x+f[i][0],y+f[i][1],count); //如此深入
visit[x][y]=0;
}
}
}
}
int main()
{
int n,m;
while(cin>>n>>m)
{
memset(a,0,sizeof(a));
memset(visit,0,sizeof(0));
int i,j;
mmin=50000;
char s;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>s;
if(s=='a')
{
ax=i;ay=j;a[i][j]=3;
}
else if(s=='r') a[i][j]=4;
else if(s=='.') a[i][j]=1;
else if(s=='x') a[i][j]=2;
}
dfs(ax,ay,0);
if(mmin==50000)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else cout<<mmin-1<<endl;
}
}
//下面是BFS：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int a[202][202]; int ax,ay;int f[4][2]={0,1,1,0,-1,0,0,-1};int mmin=50000;int visit[202][202];
struct state
{
int x,y;
int count;
state(){count=0;}
};
void bfs(state aa)
{
queue<state>q;
q.push(aa);
while(!q.empty())
{
state now=q.front(); //对队头元素分析
visit[now.x][now.y]=1; //标记访问
q.pop();
if(a[now.x][now.y]==4) //更新
{
if(now.count<mmin)mmin=now.count;
}
else
{
for(int i=0;i<4;i++) //队头拉出其他元素
{
state next;
next.x=now.x+f[i][0],next.y=now.y+f[i][1] ; //没访问或者不被限制的
if(a[next.x][next.y]==1||a[next.x][next.y]==4)next.count=now.count+1;
else if(a[next.x][next.y]==2)next.count=now.count+2;
if(visit[next.x][next.y]==0&&a[next.x][next.y]!=0)
{
q.push(next);
}
}
}
}
}
int main()
{
int n,m;
while(cin>>n>>m)
{
memset(a,0,sizeof(a));
memset(visit,0,sizeof(visit));
int i,j;
mmin=50000;
char s;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>s;
if(s=='a')
{
ax=i;ay=j;a[i][j]=3;
}
else if(s=='r') a[i][j]=4;
else if(s=='.') a[i][j]=1;
else if(s=='x') a[i][j]=2;
}
state aa;
aa.x=ax;aa.y=ay;aa.count=0;
bfs(aa);
if(mmin==50000)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
else cout<<mmin<<endl;
}
}
最新文章
- 如何设置Oracle客户端与服务器的字符集一致
- iOS MVC, MVVM
- [资料]mysql实现地理位置搜索
- linux命令缩写及全称
- mac 下真机调试 android 手机
- app开发之deviceone
- tableview直接滚动至最后一行的问题
- php 获取后缀的几种方法
- 让AllocateHwnd接受一般函数地址作参数
- #maven解决乱码问题
- label语句和break continue的使用(高程第三章)
- 有关数据传输GET和POST的方法的区别
- SQL 杂活
- Django之Ajax文件上传
- servletContext和request对象的生命周期比较
- cstdlib和stdlib.h区别
- python2中在sqlite3中插入中文
- 09 shell脚本程序练习
- Java 中>>和>>>的区别
- 2012关闭ECN