HDU 2612 Find a way

 
//2612 Find a way   
//題意:給一幅圖，有牆，有KFC，有路。兩個人要去KFC約會，有很多個KFC，問兩個人去一間KFC總共走的最少步數   
//廣搜水題，居然被初始化卡了兩個鐘悲劇了。。。對兩個人進行BFS，相加步數即可，在網上看到不少人單獨寫了兩個BFS，用兩個單獨的二維數組去存步數，可以是可以，但是如果真正理解BFS的話，一個BFS一個二維數組就可以了，沒有分開的必要，又節約了50行代碼量和200*200*4個字節的空間，O(∩_∩)O~   
#include<iostream>   
#include<queue>   
#define MAXN 0x3fffffff;   
using namespace std;  
  
int n, m;  
char map[210][210];  
int cnt[210][210];  
int cnt2[210][210];  
int visited[210][210];  
int vec[4][2]={{0,1},{-1,0},{1,0},{0,-1}};  
  
struct node  
{  
    int x;  
    int y;  
    int step;  
    bool check()  
    {  
        if (x>=0 && x<n && y>=0 && y<m)  
            return true;  
        return false;  
    }  
}Y, M;  
  
void BFS(node start, int num)  
{  
    memset(visited, 0, sizeof(visited));  
    queue<node> Q;  
    Q.push(start);  
    visited[start.x][start.y] = true;  
    while(!Q.empty())  
    {  
        node q = Q.front();  
        Q.pop();  
        for (int i = 0; i<4; i++)  
        {  
            node p = q;  
            p.x = q.x + vec[i][0];  
            p.y = q.y + vec[i][1];  
            p.step ++;  
            if (p.check() && map[p.x][p.y] != '#' && !visited[p.x][p.y])  
            {  
                visited[p.x][p.y] = true;  
                Q.push(p);  
                if (map[p.x][p.y] == '@')  
                {  
                    //BFS精粹   
                    if (num == 1)  
                        cnt[p.x][p.y] = p.step;//第一次   
                    else  
                        cnt[p.x][p.y] += p.step;//第二次   
                }  
            }  
        }  
    }  
}  
  
int main()  
{  
    while (cin>>n>>m)  
    {  
        for (int i = 0; i<n; i++)  
        {  
            for (int j = 0; j<m; j++)  
            {  
                cin>>map[i][j];  
                if (map[i][j] == 'Y')  
                {  
                    Y.x = i;  
                    Y.y = j;  
                    Y.step = 0;  
                }  
                if (map[i][j] == 'M')  
                {  
                    M.x = i;  
                    M.y = j;  
                    M.step = 0;  
                }  
            }  
        }  
          
        for (i = 0; i<n; i++)  
            for (int j = 0; j<m; j++)  
               cnt[i][j] = cnt2[i][j] = MAXN;  
        BFS(Y, 1);  
        BFS(M, 2);  
  
        int min = MAXN;  
        for (i = 0; i<n; i++)  
        {  
            for (int j = 0; j<m; j++)  
            {  
                if (map[i][j] == '@' && (cnt[i][j] < min))  
                    min =  cnt[i][j];  
            }  
        }  
        cout<<min * 11<<endl;  
    }  
    return 0;  
}  

//2612 Find a way
//題意:給一幅圖，有牆，有KFC，有路。兩個人要去KFC約會，有很多個KFC，問兩個人去一間KFC總共走的最少步數
//廣搜水題，居然被初始化卡了兩個鐘悲劇了。。。對兩個人進行BFS，相加步數即可，在網上看到不少人單獨寫了兩個BFS，用兩個單獨的二維數組去存步數，可以是可以，但是如果真正理解BFS的話，一個BFS一個二維數組就可以了，沒有分開的必要，又節約了50行代碼量和200*200*4個字節的空間，O(∩_∩)O~
#include<iostream>
#include<queue>
#define MAXN 0x3fffffff;
using namespace std;

int n, m;
char map[210][210];
int cnt[210][210];
int cnt2[210][210];
int visited[210][210];
int vec[4][2]={{0,1},{-1,0},{1,0},{0,-1}};

struct node
{
	int x;
	int y;
	int step;
	bool check()
	{
		if (x>=0 && x<n && y>=0 && y<m)
			return true;
		return false;
	}
}Y, M;

void BFS(node start, int num)
{
   	memset(visited, 0, sizeof(visited));
	queue<node> Q;
	Q.push(start);
	visited[start.x][start.y] = true;
	while(!Q.empty())
	{
		node q = Q.front();
		Q.pop();
		for (int i = 0; i<4; i++)
		{
			node p = q;
			p.x = q.x + vec[i][0];
			p.y = q.y + vec[i][1];
			p.step ++;
			if (p.check() && map[p.x][p.y] != '#' && !visited[p.x][p.y])
			{
				visited[p.x][p.y] = true;
				Q.push(p);
				if (map[p.x][p.y] == '@')
				{
					//BFS精粹
					if (num == 1)
						cnt[p.x][p.y] = p.step;//第一次
					else
						cnt[p.x][p.y] += p.step;//第二次
				}
			}
		}
	}
}

int main()
{
	while (cin>>n>>m)
	{
		for (int i = 0; i<n; i++)
		{
			for (int j = 0; j<m; j++)
			{
				cin>>map[i][j];
                if (map[i][j] == 'Y')
				{
					Y.x = i;
					Y.y = j;
					Y.step = 0;
				}
				if (map[i][j] == 'M')
				{
					M.x = i;
					M.y = j;
					M.step = 0;
				}
			}
		}
		
		for (i = 0; i<n; i++)
	    	for (int j = 0; j<m; j++)
			   cnt[i][j] = cnt2[i][j] = MAXN;
		BFS(Y, 1);
		BFS(M, 2);

		int min = MAXN;
		for (i = 0; i<n; i++)
		{
			for (int j = 0; j<m; j++)
			{
				if (map[i][j] == '@' && (cnt[i][j] < min))
					min =  cnt[i][j];
			}
		}
		cout<<min * 11<<endl;
	}
	return 0;
}