首页 > ACM题库 > HDU-杭电 > HDU 1252 Hike on a Graph-BFS-[解题报告] C++
2013
12-04

HDU 1252 Hike on a Graph-BFS-[解题报告] C++

Hike on a Graph

问题描述 :

"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.

输入:

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.

输出:

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.

样例输入:

3 1 2 3
r b r
b b b
r b r
2 1 2 2
y g
g y
0

样例输出:

2
impossible

这道题主要是要看懂这句话

the piece may only be moved along arrows of the same colour as the arrow between the two opponents’ pieces

意思是说 有3个小块 小块1想移动到小块2 去的条件是 1->2中路线的颜色和2<->3的颜色相同

 

理解了就好做了 普通的广搜,单步调试得我很郁闷,坑爹啊!

 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<string>
#define inf 0x7fffffff
#define maxn 60
using namespace std;
char maze[maxn][maxn];
int vis[maxn][maxn][maxn];
int n,a,b,c;
struct node
{
    int x,y,z;
};

int bfs()
{
    queue<node> q;
    while(!q.empty())
    q.pop();
    memset(vis,0,sizeof(vis));
    node s;
    s.x=a,s.y=b,s.z=c;
    vis[a][b][c]=1;
    q.push(s);
    node cur,next;
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(cur.x==cur.y&&cur.y==cur.z)
        return vis[cur.x][cur.y][cur.z]-1;
        for(int i=1;i<=n;i++)
        {
            if(maze[cur.x][cur.y]==maze[cur.z][i]&&!vis[cur.x][cur.y][i])
            {
                vis[cur.x][cur.y][i]=vis[cur.x][cur.y][cur.z]+1;
                next.x=cur.x,next.y=cur.y,next.z=i;
                q.push(next);
            }
            if(maze[cur.z][cur.x]==maze[cur.y][i]&&!vis[cur.x][i][cur.z])
            {
                vis[cur.x][i][cur.z]=vis[cur.x][cur.y][cur.z]+1;
                next.x=cur.x,next.y=i,next.z=cur.z;
                q.push(next);
            }
            if(maze[cur.y][cur.z]==maze[cur.x][i]&&!vis[i][cur.y][cur.z])
            {
                vis[i][cur.x][cur.y]=vis[cur.x][cur.y][cur.z]+1;
                next.x=i,next.y=cur.y,next.z=cur.z;
                q.push(next);
            }
        }
    }
    return -1;
}

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n)==1&&n)
    {
        scanf("%d%d%d",&a,&b,&c);
        getchar();
        int i,j;
        char ch;
        for(i=1;i<=n;i++)
        {
        for(j=1;j<=n;j++)
        {
            scanf("%c%c",&maze[i][j],&ch);
        }
        }
        int ans=bfs();
        if(ans!=-1)
        printf("%d\n",ans);
        else
        printf("impossible\n");
    }
    return 0;
}

 


,
  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。