Find a way
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 32255 Accepted Submission(s): 10327
Problem Description
Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.
Input
The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF
Output
For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
Sample Input
4 4
Y.#@
…
.#…
@…M
4 4
Y.#@
…
.#…
@#.M
5 5
Y…@.
.#…
.#…
@…M.
#…#
Sample Output
66
88
66
题目大意：Y和M要一起去@，他们可以上下左右移动，每次移动需要11分钟，问他们到达@的最少时间，#是不可移动。
本来以为一个小时就可以写完了硬生生写了两个小时，很多很恶心的情况开始没有考虑进来，比如@是可以走的
sample input：
2 2
@@
YM
还有Y还是可以经过M的，M也可以经过Y的，然后这个还好写，@可以走这个不太好写，最后想了想还是写出来了，这题就是两个bfs，一个从起点扫，一个从终点扫，把他们打@的距离存起来求个最小值就行了，还需要一个数组存@的坐标的步数，这里我用的一个三维数组存的（第一次用三维数组），每个点只能访问一次，需要一个vis数组记录是否访问，还需要一个step数组记录步数，其他就是常规bfs操作了。
代码：
#include<cstdio>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
const int maxn=1e3+10;
int n,m;
char str[maxn][maxn];
int vis[maxn][maxn];
int step[maxn][maxn];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node{
int x,y;
node(int a,int b):x(a),y(b){}
node(){}
};
int ans[maxn][maxn][1];
int ans1[maxn][maxn][1];
void nin(){
memset(vis,0,sizeof(vis));
memset(step,0,sizeof(step));
}
void bfs(int x1,int y1,int x2,int y2){
node test[maxn];
int cnt=0;
queue<node>st;
queue<node>qt;
st.push(node(x1,y1));
step[x1][y1]=0;
vis[x1][y1]=1;
while(!st.empty()){
int fxx=st.front().x;
int fyy=st.front().y;
st.pop();
for(int i=0;i<4;i++){
int fx=fxx+dir[i][0];
int fy=fyy+dir[i][1];
if(fx<0||fy<0||fx>=n||fy>=m)continue;
if(((str[fx][fy]=='.'||str[fx][fy]=='M')&&!vis[fx][fy])){
vis[fx][fy]=1;
step[fx][fy]=step[fxx][fyy]+1;
st.push(node(fx,fy));
}
if(str[fx][fy]=='@'&&str[fxx][fyy]!='@'){
step[fx][fy]=step[fxx][fyy]+1;
st.push(node(fx,fy));
}
if(str[fx][fy]=='@'&&!vis[fx][fy]){
test[cnt].x=fx;
test[cnt++].y=fy;
step[fx][fy]=step[fxx][fyy]+1;
// cout<<"("<<fx<<", "<<fy<<")"<<endl;
// cout<<step[fx][fy]<<endl;
vis[fx][fy]=1;
ans[fx][fy][0]=step[fx][fy];
}
}
}
// cout<<cnt<<endl;
nin();
step[x2][y2]=0;
vis[x2][y2]=1;
qt.push(node(x2,y2));
while(!qt.empty()){
int fxx=qt.front().x;
int fyy=qt.front().y;
qt.pop();
for(int i=0;i<4;i++){
int fx=fxx+dir[i][0];
int fy=fyy+dir[i][1];
if(fx<0||fy<0||fx>=n||fy>=m)continue;
if(((str[fx][fy]=='.'||str[fx][fy]=='M')&&!vis[fx][fy])){
vis[fx][fy]=1;
step[fx][fy]=step[fxx][fyy]+1;
qt.push(node(fx,fy));
}
if(str[fx][fy]=='@'&&str[fxx][fyy]!='@'){
step[fx][fy]=step[fxx][fyy]+1;
qt.push(node(fx,fy));
}
if(str[fx][fy]=='@'&&!vis[fx][fy]){
step[fx][fy]=step[fxx][fyy]+1;
vis[fx][fy]=1;
ans1[fx][fy][0]=step[fx][fy];
// cout<<"("<<fx<<", "<<fy<<")"<<endl;
// cout<<step[fx][fy]<<endl;
}
}
}
vector<int>ve;
for(int i=0;i<cnt;i++){
int fx=test[i].x;
int fy=test[i].y;
ve.push_back(ans[fx][fy][0]+ans1[fx][fy][0]);
}
sort(ve.begin(),ve.end());
cout<<ve[0]*11<<endl;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
getchar();
nin();
int x1,x2,y1,y2;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf(" %c",&str[i][j]);
if(str[i][j]=='Y'){
x1=i;y1=j;
}else if(str[i][j]=='M'){
x2=i;y2=j;
}
}
}
bfs(x1,y1,x2,y2);
}
}
京公网安备 11010502036488号