HDU 1252 : Hike on a Graph-

​​題目傳送門​​

題目大意：

有一張圖，上面的路徑都是着色的，開始的時候有3個盤子在确定的點上，現在讓你按要求沿圖中的路徑移動盤子（一步隻能移動一隻盤子），問是否能将3個盤子都移到同一個點上，如果可以，輸出需要的最少步數，否則輸出“impossible”。移動條件是：每個盤子隻能沿着這樣一條路移動，這條路的顔色和另外的兩個盤子之間的路徑上标記的顔色是一樣的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<list> 
using namespace std;
const int INF=0x3f3f3f3f;  //一般認為無窮大 
#define MEM(a,x) memset(a,x,sizeof(a)) 
#define F(i,n) for(i=1;i<=n;i++)
int cnt[55][55][55];  //記錄每個位置的最小步數 
char map[55][55];  //存圖 
bool isok;  //存儲是否可以移動到一起的結果 
int n,p1,p2,p3; 
struct Point{
    int x,y,z;
    Point(int x_=0,int y_=0,int z_=0):x(x_),y(y_),z(z_){
    }
};  /*BFS中queue的成員，用來存儲位置 ，結構體中的構造函數友善直接将位置push到queue中 */
typedef Point P; 
//Point結構體變量以後可以直接用P定義，友善一點 
int BFS()
{
    fill(&cnt[0][0][0],&cnt[0][0][0]+55*55*55,INF);
//cnt數組初始指派無窮大 
    cnt[p1][p2][p3]=0;//初始點為0步 
    queue<P>que;
    P p;
    int x,y,z;
    int i;
    int cnt_type;  //記錄步數，友善下一步操作 
    string color;  //記錄一個點的是以的邊的顔色 
    char color_mid;  //記錄另外兩個之間的顔色 
    que.push(P(p1,p2,p3));  //初始位置入隊 
    isok=false;  //還沒有移動到一起，為false 
    while(!que.empty())
    {
        p=que.front();
        que.pop();
        x=p.x;
        y=p.y;
        z=p.z;
        if(x==y&&y==z)
        {
            isok=true;  //移動到一起，為true 
            return x;  //傳回下标，友善在main方法中輸出步數 
        }
        else{
            cnt_type=cnt[x][y][z];  //目前位置步數 
            cnt_type++;  //更新位置步數=目前位置步數+1
    
             //分别 向x,y,z移動
            color_mid=map[y][z];  //點yz之間的顔色 
            color=map[x];  //點x是以邊的顔色 
            F(i,n)
            {
    if(color[i]==color_mid&&i!=x&&cnt[i][y][z]>cnt_type)
                /*點x移動的邊顔色和點yz之間的顔色相同 ，并且不同點，并且小于其原來的步數*/ 
                {
                    cnt[i][y][z]=cnt_type;  //指派更新位置的步數 
                    que.push(P(i,y,z));  //加入更新的位置 
                }
            }
            //下面一樣 
            color_mid=map[x][z];
            color=map[y];
            F(i,n)
            {
 if(color[i]==color_mid&&i!=y&&cnt[x][i][z]>cnt_type)
                {
                    cnt[x][i][z]=cnt_type;
                    que.push(P(x,i,z));
                }
            }
            color_mid=map[x][y];
            color=map[z];
            F(i,n)
            {
 if(color[i]==color_mid&&i!=z&&cnt[x][y][i]>cnt_type)
                {
                    cnt[x][y][i]=cnt_type;
                    que.push(P(x,y,i));
                }
            }
        }
    }
    return -1;
}
int main()
{
    while(cin>>n&&n)
    {
        int i,j;
        cin>>p1>>p2>>p3;
        F(i,n)
        {
          map[i][0]=' ';
        /*需要加上，經驗吧，不加，可能錯，因為不同的編譯器，
        可能有不同的預設值 ，有可能沒有值，是以賦給string變量可能會出錯 */ 
          F(j,n)
          {
            cin>>map[i][j];
    /*比較少的輸入輸出用 c++的io個人感覺比較好，
    雖然對時間效率不友好，但是對輸入輸出方式很友好，因為輸出中有空格*/ 
          }
          map[i][n+1]='\0';  //結束字元，因為要賦給string變量 
        }
        //存圖 
        int end=BFS();
        if(isok)
        printf("%d\n",cnt[end][end][end]);
        else
        {
            printf("impossible\n");
        }
    }
    return 0;
}