提交判断的链接 题目提交ＨＤＵ
HDU 或 HDOJ 2612 Find a way (两次 BFS)
#include <iostream> //结果正确，提交AC #include <cstdio> #include <cstring> #include <queue> using namespace std; #define maxn 210 int step1[maxn][maxn]; //记录Y走的步数 int step2[maxn][maxn]; //记录W走的步数 int visit[maxn][maxn]; //标记走过与否 char tu[maxn][maxn]; struct node{ //便于向队列中插入二维坐标 int x,y; }st1,st2; int dx[]={1,0,-1,0}; //指定四个方向（下右上左） int dy[]={0,1,0,-1}; int n,m; int check(int x,int y) { if(x<n && x>=0 && y<m && y>=0 && ! visit[x][y] && tu[x][y]!='#') return 0; return 1; //代表越界 } void BFS(node st,int step[][210]) //BFS的模板 { queue<node>Q; //BFS不同于DFS，BFS不用递归调用自己。while即可遍历全部 Q.push(st); visit[st.x][st.y]=1; while(!Q.empty()){ node t=Q.front();//固定格式，取值然后弹出 Q.pop(); for(int i=0;i<4;i++){ node temp; temp.x = t.x + dx[i]; temp.y = t.y + dy[i]; if(check(temp.x , temp.y))//如果越界 continue; Q.push(temp); step[temp.x][temp.y]=step[t.x][t.y]+1; //层数加一 visit[temp.x][temp.y]=1; } } return ; } int main() { while(cin>>n>>m){ for(int i=0;i<n;i++){ scanf("%s",tu[i]); for(int j=0;j<m;j++){ if(tu[i][j]=='Y'){ st1.x=i;st1.y=j; } if(tu[i][j]=='M'){ st2.x=i;st2.y=j; } } } memset(visit,0,sizeof(visit)); memset(step1,0,sizeof(step1)); BFS(st1,step1); //向step1数组中存入数据 memset(visit,0,sizeof(visit)); memset(step2,0,sizeof(step2)); BFS(st2,step2); //向step2数组中存入数据 int ans=maxn; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int t1 = step1[i][j]; int t2 = step2[i][j]; if(tu[i][j]=='@' && t1!=0 && t2!=0){ //求解过程 if(t1 +t2 < ans) ans=t1+t2; } } } cout<<ans*11<<endl; } return 0; }希望有所帮助！
