相约KFC
XJOI - 题目ID：15703必做题100分
最新提交：
Time Limit Exceeded
0 分
历史最高：
Time Limit Exceeded
0 分
时间限制: 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
数据范围
见题面
脑袋短路了，代码见下
#include<bits/stdc++.h>
using namespace std;
int n,m,o[2]={40005,40005},dx[4]{0,1,0,-1},dy[4]={1,0,-1,0};
bool h[205][205];
char s[205][205];
void fo(int x,int y,int g1,int g2,int l,int v){
if(x == g1 && y == g2){
if(o[v]>l){
o[v] = l;
}
return;
}
for(int i = 0; i<4; i++){
int s1=dx[i]+x,s2=dy[i]+y;
if(s1<n && s1>=0 && s2<m && s2>=0 && h[s1][s2] == false && s[s1][s2] != '#'){
h[s1][s2] = true;
fo(s1,s2,g1,g2,l+1,v);
h[s1][s2] = false;
}
}
}
int main(){
cin>>n>>m;
int a,b,c,d,e,f;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
cin>>s[i][j];
if(s[i][j] == '@'){
a = i;
b = j;
}else if(s[i][j] == '&'){
c = i;
d = j;
}else if(s[i][j] == 'F'){
e = i;
f = j;
}
}
}
fo(a,b,e,f,0,0);
memset(h,false,sizeof(h));
fo(c,d,e,f,0,1);
if(o[0]<180 && o[1]<180){
cout<<max(o[0],o[1]);
}
return 0;
}