一.入门级
P1747 好奇怪的游戏
P1747 好奇怪的游戏
题目描述
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？
思路： 基础的入门题
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#include<deque>
#include<queue>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=1e3+1;
const int mod=1e9+7;
using namespace std;
struct node
{
int x,y,step;
node(int a=0,int b=0,int c=0)//结构体函数
{
x=a,y=b,step=c;
}
};
int dx[12]={1,1,2,2,2,2,-1,-1,-2,-2,-2,-2};//走法
int dy[12]={-2,2,-2,-1,1,2,-2,2,-1,1,-2,2};
int x1,x2,y_1,y2;
bool vis[maxn][maxn];//标记是否走过
queue<node>q;//队列实现bfs
void bfs(int a,int b)
{
q.push(node(a,b,0));//放
vis[a][b]=true;//标
while(!q.empty())
{
node nn=q.front();//取
q.pop();//扔
for(int i=0;i<12;i++)
{
int nx=nn.x+dx[i];//走
int ny=nn.y+dy[i];
if(nx>0&&ny>0&&!vis[nx][ny]&&nx<100&&ny<100)//判
{
q.push(node(nx,ny,nn.step+1));//放
vis[nx][ny]=true;//标
}
if(nx==1&&ny==1)//判
{
cout<<nn.step+1<<endl;
return;
}
}
}
}
int main()
{
cin>>x1>>y_1>>x2>>y2;
bfs(x1,y_1);
memset(vis,false,sizeof(vis));
while(!q.empty())q.pop();//清空
bfs(x2,y2);
return 0;
}
另一种思路： dfs+记忆化搜素
#include<bits/stdc++.h>
using namespace std;
int x,y,f[30][30];
//f[i][j]:从i,j走到1,1所需的最小步数
int dx[13]={0,-2,-2,+2,+2,-1,-1,+1,+1,-2,-2,+2,+2};
int dy[13]={0,-1,+1,-1,+1,-2,+2,-2,+2,-2,+2,-2,+2};
//马字8个方向，田字4个方向
void dfs(int x,int y,int step) //记忆化搜索，走到x,y花了step步
{
f[x][y]=step; //更新最小步数
for (int i=1;i<=12;i++) //12个方向走一遍
{
int xx=x+dx[i];
int yy=y+dy[i];
if (xx>=1&&xx<=20&&yy>=1&&yy<=20&&(f[xx][yy]==0||f[xx][yy]>step+1)) dfs(xx,yy,step+1);
//如果没超出边界并且xx,yy可以被更新，就继续走
}
}
int main()
{
for (int i=1;i<=2;i++)
{
scanf("%d%d",&x,&y);
memset(f,0,sizeof(f));
dfs(x,y,0); //走到x,y需要0步
printf("%d\n",f[1][1]); //最后输出
}
return 0;
}
赞，dfs天下第一，能用dfs就不用bfs
链接：https://ac.nowcoder.com/acm/contest/322/B
来源：牛客网
TRDD got lost again
TRDD got lost again
题目描述
X城市是一个交通十分不便利的城市，城市可以看成一个n * m大小的矩阵， 现在TRDD手里有该城市的地图:一个2*n+1行, 2 *m+1列大小的地图。现在TRDD所在的格子用S表示,机场所在的格子用T表示。 其他格子用空格表示，地图上左右相邻的两个格子如果不能通行用"|“表示， 上下相邻的两个点如果不能通行用”-“表示，”+“表示格子的四个角。 题目保证城市X最外圈无法通行（具体请看样例输入）。 为了能尽快赶到机场，TRDD想请你帮忙计算出他到达机场最少需要走过多少个格子（包括起点S和终点T）。 如果无法到达机场T，则输出"TRDD Got lost…TAT”(不包括双引号)。
输入描述:
第一行读入两个数n, m（1 <= n, m <= 3000)表示X城市的大小。之后有2 * n + 1行， 每行有2 * m + 1个字符， 用来表示TRDD手里的地图题目保证S和T都有且仅有一个。
输出描述:
如果TRDD能到达机场， 则输出TRDD最少需要经过几个格子否则输出"TRDD Got lost…TAT"(不包括双引号)
输入：
4 3
+-+-+-+
|S| | |
+ +-+-+
| | | |
+ +-+-+
| |T |
+ +-+ +
| |
+-+-+-+
输出：8
由于数据量过大，建议不要使用scanf("％c")读入，否则可能会TLE。
思路：此题细节颇多，注意c++11可以用gets(),而c++14却不能用（gets有安全隐患故删除）
#include<bits/stdc++.h>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=6005;
const int mod=1e9+7;
using namespace std;
int n,m,nx,ny,steps,ans,tx,ty,sx,sy;
inline int read()
{
int x=0,f=0;
char ch=getchar();
while(ch>'9'||ch<'0'){f|=(ch=='-');ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return f?-x:x;
}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool vis[maxn][maxn];
char mp[maxn][maxn];
struct node
{
int x,y,step;
node(int a=0,int b=0,int c=0)
{
x=a,y=b,step=c;
}
};
queue<node>q;
void bfs(int x,int y)
{
vis[x][y]=true;
q.push(node(x,y,1));
while(!q.empty())
{
nx=q.front().x;
ny=q.front().y;javascript:void(0);
steps=q.front().step;
q.pop();
for(int i=0;i<4;i++)
{
int xx=nx+dx[i];
int yy=ny+dy[i];
if(xx>0&&yy>0&&xx<=n&&yy<=m&&!vis[xx][yy]&&(mp[xx][yy]=='T'||mp[xx][yy]==' '))
{
q.push(node(xx,yy,steps+1));
javascript:void(0); vis[xx][yy]=true;
}
if(mp[xx][yy]=='T')
{
cout<<(steps+2)/2<<endl;
return ;
}
}
}
printf("TRDD Got lost...TAT\n");
}
int main()
{
memset(vis,false,sizeof(vis));
//n=read(),m=read();//快读就不需要加getchr()快读万岁！！；
cin>>n>>m;
getchar();//注意必须要有这个getcgar()！！;
m=2*m+1;
n=2*n+1;
int flag=0;
for(int i=1;i<=n;i++)
{
gets(mp[i]);
if(!flag)
for(int j=1;j<=m;j++)
if(mp[i][j]=='S'){sx=i,sy=j;flag=1;}
}
bfs(sx,sy);
return 0;
}
二.进阶
final的BFS Abbott’s Revenge
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧
京公网安备 11010502036488号