HDU 1242 dFS 找目标最短路
//多个起点，要最短得目标，不妨倒过来从目标出发，去找最近的点更新！！！！！！递归时思路要清楚
#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;
}
}
优质内容筛选与推荐>>
1、菜根谭#52
2、tomcat和jvm调优
3、dede后台文章不能上传图片及缩略图的解决办法
4、dreamweaver教程：怎么制作网页滚动字幕
5、我看博客园之争论