SDUT--找朋友（BFS&&DFS）
2024-09-07 10:18:07
找朋友
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描写叙述
X，作为户外运动的忠实爱好者，总是不想呆在家里。如今，他想把死宅Y从家里拉出来。问从X的家到Y的家的最短时间是多少。
为了简化问题，我们把地图抽象为n*n的矩阵。行编号从上到下为1 到 n，列编号从左到右为1 到 n。
矩阵中’X’表示X所在的初始坐标。’Y’表示Y的位置 , ’#’表示当前位置不能走。’ * ’表示当前位置能够通行。X每次仅仅能向上下左右的相邻的 ’*’ 移动，每移动一次耗时1秒。
输入
多组输入。每组測试数据首先输入两个整数n。m(1<= n ,m<=15 )表示地图大小。
接下来的n 行，每行n个字符。保证输入数据合法。
输出
若X能够到达Y的家，输出最少时间，否则输出 -1。
演示样例输入
3 3
X#Y
***
#*#
3 3
X#Y
*#*
#*#
演示样例输出
4
-1
提示
4个搜索方向，上下左右，感觉dfs不太适合这类题，太慢。尤其是按不同的搜索顺序，比方按上下右左搜，居然TLE。。
略微调了一下方向 70ms过
bfs就好多了，搜到了直接退出。
#include <cstdio>//BFS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char ma[20][20];
bool vis[20][20];
typedef struct node
{
int x;
int y;
int time;
};
int n,m;
int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(int x,int y)
{
queue <node> Q;
node t;
t.x=x;t.y=y;t.time=0;
Q.push(t);
vis[x][y]=1;
while(!Q.empty())
{
node v=Q.front();Q.pop();
if(ma[v.x][v.y]=='Y')
{
cout<<v.time<<endl;
return ;
}
for(int i=0;i<4;i++)
{
t.x=v.x+mov[i][0];
t.y=v.y+mov[i][1];
if(0<=t.x&&t.x<n&&0<=t.y&&t.y<m&&!vis[t.x][t.y]&&ma[t.x][t.y]!='#')
{
t.time=v.time+1;
vis[t.x][t.y]=1;
Q.push(t);
}
}
}
puts("-1");
} int main()
{
int i,j;
while(cin>>n>>m)
{
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
cin>>ma[i];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(ma[i][j]=='X')
break;
}
if(j<m)
break;
}
bfs(i,j);
}
return 0;
}
#include <cstdio>//DFS
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
const int INF=1<<20; struct node
{
int x,y,ans;
};
char ma[16][16];
int vis[16][16];
int n,m,mi;
int mv[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void DFS(int x,int y,int ans)
{
if(ans>=mi)
{
return ;
}
if(ma[x][y]=='Y')
{
if(ans<mi)
{
mi=ans;
}
return ;
}
node f;
for(int i=0;i<4;i++)
{
f.x=x+mv[i][0];
f.y=y+mv[i][1];
if(0<=f.x&&f.x<n&&0<=f.y&&f.y<m&&!vis[f.x][f.y]&&ma[f.x][f.y]!='#')
{
vis[f.x][f.y]=1;
DFS(f.x,f.y,ans+1);
vis[f.x][f.y]=0;
}
}
}
int main()
{ while(~scanf("%d%d",&n,&m))
{
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
scanf("%*c%s",ma[i]);
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(ma[i][j]=='X')
{
break;
}
}
if(j<m)
break;
}
mi=INF;
vis[i][j]=1;
DFS(i,j,0);
if(mi<INF)
printf("%d\n",mi);
else
puts("-1");
}
return 0;
}
最新文章
- 【基于WPF+OneNote+Oracle的中文图片识别系统阶段总结】之篇四：关于OneNote入库处理以及审核
- POJ 3278 Catch That Cow
- Java 并发-访问量
- Tuple初探
- chrome 如何卸载干净
- 毕业设计——Django邮件发送功能实现及问题记录
- java控制台连接数据库
- jquery.ocupload上传文件到指定目录
- 卷积运算的本质，以tensorflow中VALID卷积方式为例。
- LintCode: Convert Sorted Array to Binary Search Tree With Minimal Height
- OpenCV Error: Insufficient memory问题解析
- JQuery判断form表单是否为空
- Elasticsearch 相关 api 操作
- STL标准库-容器-vector
- Python学习——编程语言介绍
- 开始整理iOS职位面试问题及答案
- 三个缓存数据库Redis、Memcache、MongoDB
- docker动态添加磁盘
- 编写可维护的JavaScript----笔记（三）
- Luogu 3302 [SDOI2013]森林