HDU 2612

题目
求最短路,最小值最好用bfs。
这道题目的代码,本菜鸡写的比较傻。

#include <cstdio>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=202;
char maze[maxn][maxn];
int n, m, ans=1000;
int d1[maxn][maxn], d2[maxn][maxn];
typedef pair<int, int> p;
p st1, st2;
int fx[4]={-1, 1, 0, 0}, fy[4]={0, 0, -1, 1};
bool judge(int u, int v){
	if(maze[u][v]=='#')
		return false;
	if(u<0 || u>=n || v<0 || v>=m)
		return false;

	return true;
}

void bfs1(p st){
	queue<p> q;
	q.push(st);

    d1[st.first][st.second]=0;
	while(!q.empty()){
		p top=q.front();
		q.pop();

        //printf("%d %d\n", top.first, top.second);
        for(int i=0; i<4; i++){
        	p temp;
        	temp.first=top.first+fx[i];
        	temp.second=top.second+fy[i];

        	if(judge(temp.first, temp.second) && d1[temp.first][temp.second]==-1){
        		d1[temp.first][temp.second]=d1[top.first][top.second]+1;
        		q.push(temp);
        	}
        }
	}
}

void bfs2(p st){
	queue<p> q;
	q.push(st);

    d2[st.first][st.second]=0;
	while(!q.empty()){
		p top=q.front();
		q.pop();

        for(int i=0; i<4; i++){
        	p temp;
        	temp.first=top.first+fx[i];
        	temp.second=top.second+fy[i];

        	if(judge(temp.first, temp.second) && d2[temp.first][temp.second]==-1){
        		d2[temp.first][temp.second]=d2[top.first][top.second]+1;
        		q.push(temp);
        	}
        }
	}
}

int main()
{
    while(scanf("%d%d", &n, &m)!=EOF){
    	memset(d1, -1, sizeof(d1));
    	memset(d2, -1, sizeof(d2));
        ans=1000;

    	for(int i=0; i<n; i++){
    		getchar();
    		for(int j=0; j<m; j++){
    			maze[i][j]=getchar();
    			if('Y'==maze[i][j])
    				st1.first=i, st1.second=j;
    			if('M'==maze[i][j])
    				st2.first=i, st2.second=j;
    		}
    	}

    	bfs1(st1);
    	bfs2(st2);

        for(int i=0; i<n; i++){
        	for(int j=0; j<m; j++){
        		if(maze[i][j]=='@'){
        			if(d1[i][j]>=0 && d2[i][j]>=0)//保证两个人都能到达这个点
        			    ans=min(ans, d1[i][j]+d2[i][j]);
        		}
        	}
        }

        printf("%d\n", ans*11);
    }
	return 0;
}
上一篇:HDU 6156 题解


下一篇:HDU 1312 DFS Java版