首页 > 其他分享 >HDU 1252 Hike on a Graph

HDU 1252 Hike on a Graph

时间:2022-11-09 22:33:27浏览次数:45  
标签:sz HDU int Hike three pieces game 1252 board

Problem Description "Hike on a Graph" is a game that is played on a board on which an undirected graph is drawn. The graph is complete and has all loops, i.e. for any two locations there is exactly one arrow between them. The arrows are coloured. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players may do a move. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same colour as the arrow between the two opponents' pieces. 

In the sixties ("make love not war") a one-person variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.

HDU 1252	Hike on a Graph_#include

 
Input The input file contains several test cases. Each test case starts with the number n. Input is terminated by n=0. Otherwise, 1<=n<=50. Then follow three integers p1, p2, p3 with 1<=pi<=n denoting the starting locations of the game pieces. The colours of the arrows are given next as a m×m matrix of whitespace-separated lower-case letters. The element mij denotes the colour of the arrow between the locations i and j. Since the graph is undirected, you can assume the matrix to be symmetrical. 
 
Output For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word "impossible" if that is not possible for the given board and starting locations.
 
Sample Input 3 1 2 3 r b r b b b r b r 2 1 2 2 y g g y 0  
Sample Output 2 impossible  

简单bfs,读懂题目就行了。

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int sz=55;
int f[sz][sz][sz];
int n;
char s[sz],mp[sz][sz];

struct point
{
    int x,y,z;
    point(int x=0,int y=0,int z=0):x(x),y(y),z(z){};
};

int main()
{
    while (~scanf("%d",&n),n)
    {
        point a;    scanf("%d%d%d",&a.x,&a.y,&a.z);
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                scanf("%s",s);
                mp[i][j]=s[0];
            }
        }
        memset(f,-1,sizeof(f));
        queue<point> p; p.push(a); f[a.x][a.y][a.z]=0;
        bool flag=false;
        while (!p.empty())
        {
            point q=p.front(); p.pop();
            if (q.x==q.y&&q.y==q.z) 
            {
                printf("%d\n",f[q.x][q.y][q.z]);
                flag=true; break;
            }
            for (int i=1;i<=n;i++)
            {
                if (mp[q.x][i]==mp[q.y][q.z]&&f[i][q.y][q.z]==-1)
                {
                    f[i][q.y][q.z]=f[q.x][q.y][q.z]+1;
                    p.push(point(i,q.y,q.z));
                }
                if (mp[q.y][i]==mp[q.x][q.z]&&f[q.x][i][q.z]==-1)
                {
                    f[q.x][i][q.z]=f[q.x][q.y][q.z]+1;
                    p.push(point(q.x,i,q.z));
                }
                if (mp[q.z][i]==mp[q.x][q.y]&&f[q.x][q.y][i]==-1)
                {
                    f[q.x][q.y][i]=f[q.x][q.y][q.z]+1;
                    p.push(point(q.x,q.y,i));
                }
            }
        }
        if (!flag) printf("impossible\n");
    }
    return 0;
}


标签:sz,HDU,int,Hike,three,pieces,game,1252,board
From: https://blog.51cto.com/u_15870896/5838894

相关文章

  • HDU 3345 War Chess
    ProblemDescriptionWarchessishh'sfavoritegame:Inthisgame,thereisanN*Mbattlemap,andeveryplayerhashisownMovingVal(MV).Ineach......
  • HDU 2660 Accepted Necklace
    ProblemDescriptionIhaveNpreciousstones,andplantouseKofthemtomakeanecklaceformymother,butshewon'tacceptanecklacewhichistooh......
  • HDU 1828 Picture
    ProblemDescriptionAnumberofrectangularposters,photographsandotherpicturesofthesameshapearepastedonawall.Theirsidesareallvertical......
  • HDU 3695 Computer Virus on Planet Pandora
    ProblemDescription    AliensonplanetPandoraalsowritecomputerprogramslikeus.Theirprogramsonlyconsistofcapitalletters(‘A’to‘Z’......
  • HDU 5379 Mahjong tree
    ProblemDescriptionLittlesunisanartist.Todayheisplayingmahjongalone.Hesuddenlyfeelsthatthetreeintheyarddoesn'tlookgood.Sohewant......
  • HDU 3397 Sequence operation
    ProblemDescriptionlxhgwwgotasequencecontainsncharacterswhichareall'0'sor'1's.Wehavefiveoperationshere:Changeoperations:0ab......
  • HDU 1255 覆盖的面积
    ProblemDescription给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积. Input输入数据的第一行是一个正整数T(1<=T<=100),代表测试......
  • HDU 2665 Kth number
    ProblemDescriptionGiveyouasequenceandaskyouthekthbignumberofainteval.InputThefirstlineisthenumberofthetestcases. F......
  • HDU 2715 Herd Sums
    DescriptionThecowsinfarmerJohn'sherdarenumberedandbrandedwithconsecutiveintegersfrom1toN(1<=N<=10,000,000).Whenthecowscometot......
  • HDU 5339 Untitled
    ProblemDescriptiona and n integers b1,…,bn.Afterselectingsomenumbersfrom b1,…,bn inanyorder,say c1,…,cr,wewanttom......