pair queue____多源图广搜

1、简介

        class pair ，中文译为对组，可以将两个值视为一个单元。对于map和multimap，就是用pairs来管理value/key的成对元素。任何函数需要回传两个值，也需要pair。

        该函数的相关内容如下所示：

        |->Type----->struct

        |->Include---> <utility>

        |->Define----> pair<calss first,calss second>(first,second)

        |

        |->member

        |      |------>first

        |      |------>second

        |

        |->Sub

        |      |------>constructor（default,assignment,copy)

        |

        |->Fun

        |------>operator(==,<,<=,>,>=,!=,=)

        |------>make_pair(first,second) 返回一个新的pair

     需求：

      Header: <utility>

      Namespace: std

 

2、 stl源码

pair的源码

 // TEMPLATE STRUCT pair

template<class _Ty1,

    class _Ty2> struct pair

    {// store a pair of values

    typedef pair<_Ty1, _Ty2> _Myt;

    typedef _Ty1 first_type;

    typedef _Ty2 second_type;

    pair()

        : first(_Ty1()), second(_Ty2())

        {// construct from defaults

        }

 

    pair(const _Ty1& _Val1, const _Ty2& _Val2)

        : first(_Val1), second(_Val2)

        {// construct from specified values

        }

 

    template<class _Other1,

        class _Other2>

        pair(const pair<_Other1, _Other2>& _Right)

        : first(_Right.first), second(_Right.second)

        {// construct from compatible pair

        }

 

    void swap(_Myt& _Right)

        {// exchange contents with _Right

        if (this != &_Right)

            {// different, worth swapping

            std::swap(first, _Right.first);

            std::swap(second, _Right.second);

            }

        }

    _Ty1 first;// the first stored value

    _Ty2 second;// the second stored value

    };


makepair 的源码

template<class _Ty1,

    class _Ty2> inline

    pair<_Ty1, _Ty2> make_pair(_Ty1 _Val1, _Ty2 _Val2)

    {// return pair composed from arguments

    return (pair<_Ty1, _Ty2>(_Val1, _Val2));

    }

 

3、使用范例

#include <utility> 

#include <stdio.h>

using namespace std;

int main() 

{ 

    pair<char, int> c1(L'x', 3); 

    printf("[%c, %d", c1.first, c1.second); 

 

    c1 = make_pair(L'y', 4); 

    printf("[{%c}, {%d}]", c1.first, c1.second); 

    return (0); 

} 

来源：http://hi.baidu.com/taozpwater/item/d85d81bde4fd154b2bebe34e

//UVa11624

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility> //使用pair

using namespace std;

int r,c;
int map[1010][1010];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
queue< pair<int,int> > J; //声明方式
queue< pair<int,int> > F;

void bfs()
{
    pair<int,int> JJ,FF;
    int x, y, i, time = 0, ok = 0;    

    while( !J.empty() )//火-1 墙1 能走0
    {
        time++;

        JJ = J.front();
        J.pop();   //别忘记pop             
        map[JJ.first][JJ.second] = 1;//标记访问(把这个地方变成墙就行)
        for( i = 0; i < 4; i++)//向四个方向扩展(能走的)
        {
            x = JJ.first + dir[i][0];
            y = JJ.second + dir[i][1]; //pair 具有 first 与 second 成员
            if( map[x][y] == -1 || map[x][y] == 1)//墙||火不能走
                continue;
            if( x == r || x == 0 || y == 0 || y == c )//边界则走完
            {
                ok = 1;
                printf("%d
", time);
                return;
            }
            if( map[x][y] == 0)//能走的
            {
                J.push(make_pair(x, y));//queue中插入pair   利用make_pair()方法
            }
        }

        FF = F.front();
        F.pop();                
        for( i = 0; i < 4; i++)//向四个方向扩展(会着火的)   //两种扩展有顺序,先走后火
        {
            x = FF.first + dir[i][0];
            y = FF.second + dir[i][1];
            if( map[x][y] == -1 || map[x][y] == 1)
                continue;
            if( map[x][y] == 0 || map[x][y] == 2)
            {
                map[x][y] = -1;
                F.push(make_pair(x, y));
            }
        }
    }
    if(ok == 0) printf("IMPOSSIBLE
");
}


void bfs_fire()
{
    pair<int, int> FF;
    int time, i, x, y;

    while( !F.empty() )
    {            
        FF = F.front();
        F.pop();        
        time = map[FF.first][FF.second];

        for( i = 0; i < 4; i++)
        {
            x = FF.first + dir[i][0];
            y = FF.second + dir[i][1];
            if(x >= r || x < 0 || y >= c || y < 0)//越界
                continue;            
            if( map[x][y] == 0 )
            {
                map[x][y] = time + 1;
                F.push(make_pair(x, y));
            }
        }
    }
}


int main()
{
    int N;
    int i,j;
    char temp;

    //freopen("1.txt", "r", stdin);
    scanf("%d", &N);
    getchar();
    while(N--)
    {
        while( !J.empty() ) J.pop(); //注意初始化(清空)队列
        while( !F.empty() ) F.pop();

        scanf("%d%d", &r, &c);
        getchar();

        for(i = 0; i < r; i++)
        {
            for(j = 0; j < c; j++)
            {//# = -1     F = 1     J = 2    . = 0
                scanf("%c", &temp);//当读取%c时，注意用getchar吸收掉不必要的回车
                if(temp == '#')
                    map[i][j] = -1;
                else if(temp == 'F')
                {
                    map[i][j] = 1;
                    F.push(make_pair(i,j));
                }
                else if(temp == 'J')
                {
                    map[i][j] = 2;
                    J.push(make_pair(i,j));
                }
                else
                    map[i][j] = 0;
            }
            getchar();
        }
        bfs();
    }
    return 0;
}