周子寓
(zzy10124)
1
11. 相约KFC
XJOI - 题目ID：15703100分
最新提交：
Wrong Answer
40 分
历史最高：
Wrong Answer
40 分
时间限制: 200ms
空间限制: 131072kB
题目描述
暑假即将到来，鱼大大和羊大大计划吃肯德基。他们在计划中在某一天选择了某一个肯德基吃午饭。
到了约定的日子，鱼大大和羊大大都是9点出发，向KFC前进，问他们两能否在中午12点之前到达约定的KFC？如果可以，那么他们最少花费多少分钟就能在KFC相约？
约定：
时间计算：起点到终点的距离为时间，即走1单位的距离，鱼大大和羊大大都要花费1分钟的时间。
‘@’ 是鱼大大的位置，‘＃’ 是障碍，‘F’ 表示KFC，‘＆’ 表示羊大大的位置。
‘.’，‘F’，‘@’ 和 ‘＆’，这些位置都可以通过。
输入格式
第一行包含两个整数 n 和 m。
接下来的 n 行，每行输入 m 个字符来表示地图。(1 ≤ n ≤ m ≤ 200)
输出格式
如果能找到一条可行的路径并在在12点之前到达KFC，输出花费的最少时间，否则输出 “Meeting cancelled”（两人无法在12点之前相约在此KFC）。
样例
Input 1
4 4 @.#. … .#… F…&
Output 1
3
数据范围
见题面
5 个赞
Syxqwq
(Loser_Syx)
4
第一题栈模拟加减乘除即可，每次取两个栈首。
第二题枚举删除哪一个 #，然后直接广搜。
第三题广搜两遍。
第四题的性质就是只能向右和向下走，那么因为最短路径不过 50 条，直接广搜（这个应该需要实时统计）或者深搜都可以。
5 个赞
Syxqwq
(Loser_Syx)
6
哦可能不太对，“不允许走回头路”这句话范围太广了/qd
3 个赞
周子寓
(zzy10124)
7
还有，说一句，这些思路我都知道，但代码不是W，就是T
3 个赞
潘葛宇
( 不干人事的胖鳄鱼)
9
#include<bits/stdc++.h>
using namespace std;
int maxn=INT_MIN,n,m;
int mX,mY,mfX,mfY;
char mxpn[255][255];
int vis[255][255];
int a[255][255];
int b[255][255];
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};
struct Node{
int x,y,step;
};
void bfs(int X,int Y,int arr[][255]){
queue<Node>qu;
qu.push({X,Y,0});
memset(vis,0,sizeof(vis));
vis[X][Y]=1;
while(!qu.empty()){
Node now=qu.front();
qu.pop();
for(int i=0;i<4;i++){
int now_x=now.x+dx[i];
int now_y=now.y+dy[i];
if(now_x<1||now_x>n||now_y<1||now_y>m||vis[now_x][now_y]==1||mxpn[now_x][now_y]=='#'){
continue;
}
vis[now_x][now_y]=1;
arr[now_x][now_y]=now.step+1;
qu.push({now_x,now_y,now.step+1});
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mxpn[i][j];
if(mxpn[i][j]=='@'){
mX=i;
mY=j;
}
if(mxpn[i][j]=='&'){
mfX=i;
mfY=j;
}
}
}
bfs(mX,mY,a);
bfs(mfX,mfY,b);
int minn=INT_MAX;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mxpn[i][j]=='F'&&a[i][j]!=0&&b[i][j]!=0){
minn=min(minn,a[i][j]+b[i][j]);
}
}
}
if(minn!=INT_MAX){
cout<<minn;
}else{
cout<<"Meeting cancelled";
}
return 0;
}
2 个赞
陈亮
(小黑子)
10
#include <bits/stdc++.h>
using namespace std;
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
char mp[205][205];//标记，从起点到x，y的最小步数
int n,m,a,b,c,d,e,f,t1,t2;
struct node{
int x,y,step;//从起点到x，y的最少步数
};
void bfs(int sx, int sy,int &t){//sx,sy起点的坐标t:引用
int vis[205][205]={};
queue<node>que;
vis[sx][sy]=1;
que.push({sx,sy,0});//处理起点
while(que.size()){//开始广搜,只要队列不为空,一直搜
//取队头,丢队头
node hd=que.front();
que.pop();
if(hd.x==e && hd.y==f){
t=hd.step;
return;
}
for(int i=0;i<4;i++){//遍历4个方向
int nx=hd.x+dx[i];
int ny=hd.y+dy[i];
int nestp=hd.step+1;
if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny]==1 || mp[nx][ny]=='#'){
continue;
}
vis[nx][ny]=1;
que.push({nx,ny,nestp});//处理新点1标记新点2新点入队
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='@'){
a=i;
b=j;
}
if(mp[i][j]=='&'){
c=i;
d=j;
}
if(mp[i][j]=='F'){
e=i;
f=j;
}
}
}
bfs(a,b,t1);//搜索鱼大大
bfs(c,d,t2);//搜索羊大大
if(t1>0 && t2>0 && t1<180 && t2<180){
cout<<max(t1,t2);
}
else{
cout<<"Meeting cancelled";
}
return 0;
}
2 个赞
陈亮
(小黑子)
14
#include <bits/stdc++.h>
using namespace std;
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
char mp[205][205];//标记，从起点到x，y的最小步数
int n,m,a,b,c,d,e,f,t1,t2;
struct node{
int x,y,step;//从起点到x，y的最少步数
};
void bfs(int sx, int sy,int &t){//sx,sy起点的坐标t:引用
int vis[205][205]={};
queue<node>que;
vis[sx][sy]=1;
que.push({sx,sy,0});//处理起点
while(que.size()){//开始广搜,只要队列不为空,一直搜
//取队头,丢队头
node hd=que.front();
que.pop();
if(hd.x==e && hd.y==f){
t=hd.step;
return;
}
for(int i=0;i<4;i++){//遍历4个方向
int nx=hd.x+dx[i];
int ny=hd.y+dy[i];
int nestp=hd.step+1;
if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny]==1 || mp[nx][ny]=='#'){
continue;
}
vis[nx][ny]=1;
que.push({nx,ny,nestp});//处理新点1标记新点2新点入队
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='@'){
a=i;
b=j;
}
if(mp[i][j]=='&'){
c=i;
d=j;
}
if(mp[i][j]=='F'){
e=i;
f=j;
}
}
}
bfs(a,b,t1);//搜索鱼大大
bfs(c,d,t2);//搜索羊大大
if(t1>0 && t2>0 && t1<180 && t2<180){
cout<<max(t1,t2);
}
else{
cout<<"Meeting cancelled";
}
return 0;
}
2 个赞
