bfs對路徑有條件(必須拿到某個東西)

一個bfs，但标記的數組變化一下，變成三維數組；其中一維變成标記狀态(已經拿過或者暫時沒有拿過)用的；其餘的都不變；

詳情看例子；；；

hdu2612；

題目連結；http://acm.split.hdu.edu.cn/showproblem.php?pid=2612；

題目大意；地圖裡面有YM兩個人，@kfc，#牆，.路，他們兩個人要在地圖裡面找到一個@kfc，使得兩者到它的距離之和最短；

思路；因為bfs就是最優的，就是最短的距離；是以直接使用bfs從Y到M；但是中間要保證經過@ok；否則不能；

關鍵在于怎麼實作bfs從Y到M并且經過@呢？？？？

還是使用标記方法；把普通bfs的是否走過的标記變化一下；

判斷是否走過；該題因變化成分狀态的是否走過；相同狀态的不能再入隊列了；

兩種狀态；

1；已經經過過@的；

2；暫時還沒有經過@的；

還要注意一下；這個狀态是伴随每個格子的；是以也要是結構體元素；然而要進行初始化；最開始狀态應該都是沒有經過過@的；；；怎麼在結構體裡面對元素進行初始化；

struct node
{
    int x, y,step,flag;
    node()
    {
        this->flag = ;//對每個flag進行初始化；為0；
    }
};
           

看bfs的代碼；

bool mark[][][];//又是三維數組；另外一維是标記狀态用的
void bfs()
{
    queue<node>q;
    memset(mark,,sizeof(mark));
    node now, next;
    now.x=si;now.y=sj;now.step=;
    q.push(now);
    mark[si][sj][]=;//表示si，sj這個點在沒有拿到@的經過過了；；
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        //printf("%d %d %d\n",now.x,now.y,flag);
        for(int i = ; i < ; i++)
        {
            int a = now.x+dir[i][];
            int b = now.y+dir[i][]; 
            next.flag = now.flag;//指派狀态
            if(now.x==ei && now.y==ej && now.flag == )//成功達到目的地；
            {
                printf("%d\n",now.step*);
                return ;
            }
            if(a >=  && a < n && b >=  && b < m && mp[a][b] != '#')
            {
                if(mp[a][b]=='@')
                {
                    next.flag = ;
                }
                if(mark[a][b][next.flag]==)//與普通的bfs一樣；标記作用。但這裡表示每個格子在不同狀态是否走過；一個位置有倆個狀态 
                    continue;
                next.x=a;next.y=b;next.step=now.step+;
                q.push(next);
            }
        }
    }
}
           

完整代碼；

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<stack>
#include<set>
#include<string.h>
using namespace std;
struct node
{
    int x, y,step,flag;
    node()
    {
        this->flag = ;
    }
};
char mp[][];
bool mark[][][];
int dir[][]={{,},{-,},{,},{,-}};
int n, m,si,sj,ei,ej;
void bfs()
{
    queue<node>q;
    memset(mark,,sizeof(mark));
    node now, next;
    now.x=si;now.y=sj;now.step=;
    q.push(now);
    mark[si][sj][]=;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        //printf("%d %d %d\n",now.x,now.y,flag);
        for(int i = ; i < ; i++)
        {
            int a = now.x+dir[i][];
            int b = now.y+dir[i][]; 
            next.flag = now.flag;
            if(now.x==ei && now.y==ej && now.flag == )
            {
                printf("%d\n",now.step*);
                return ;
            }
            if(a >=  && a < n && b >=  && b < m && mp[a][b] != '#')
            {
                if(mp[a][b]=='@')
                {
                    next.flag = ;
                }
                if(mark[a][b][next.flag]==)//與普通的bfs一樣；标記作用。但這裡表示每個格子在不同狀态是否走過；一個位置有倆個狀态 
                    continue;
                next.x=a;next.y=b;next.step=now.step+;
                q.push(next);
            }
        }
    }
}
int main()
{
    int i,j;
    while(~scanf("%d %d",&n,&m))
    {
        for(i = ; i < n; i++)
        {
            scanf("%s",mp[i]);
            for(j = ; j < m; j++)
            {
                if(mp[i][j]=='Y'){si=i;sj=j;}
                if(mp[i][j]=='M'){ei=i;ej=j;}
            }
        }
        bfs();
    }

    return ;
}