程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10047 - The Monocycle bfs

uva 10047 - The Monocycle bfs

編輯：C++入門知識

uva 10047 - The Monocycle bfs

題目鏈接

A monocycle is a cycle that runs on one wheel and the one we will be considering is a bit more special. It has a solid wheel colored with five different colors as shown in the figure:

The colZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcmVkIHNlZ21lbnRzIG1ha2UgZXF1YWwgYW5nbGVzICg3MjxzdXA+PGVtPm88L2VtPjwvc3VwPikgYXQgdGhlIGNlbnRlci4gQSBtb25vY3ljbGlzdCByaWRlcyB0aGlzIGN5Y2xlIG9uIGFuIDxpbWcgd2lkdGg9"61" height="32" align="MIDDLE" border="0" src="https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012113450710.gif" alt="$M \times N$">grid of square tiles. The tiles have such size that moving forward from the center of one tile to that of the next one makes the wheel rotate exactly 72^o around its own center. The effect is shown in the above figure. When the wheel is at the center of square 1, the mid-point of the periphery of its blue segment is in touch with the ground. But when the wheel moves forward to the center of the next square (square 2) the mid-point of its white segment touches the ground.

Some of the squares of the grid are blocked and hence the cyclist cannot move to them. The cyclist starts from some square and tries to move to a target square in minimum amount of time. From any square either he moves forward to the next square or he remains in the same square but turns 90^o left or right. Each of these actions requires exactly 1 second to execute. He always starts his ride facing north and with the mid-point of the green segment of his wheel touching the ground. In the target square, too, the green segment must be touching the ground but he does not care about the direction he will be facing.

Before he starts his ride, please help him find out whether the destination is reachable and if so the minimum amount of time he will require to reach it.

Input

The input may contain multiple test cases.

The first line of each test case contains two integers M and N ( $1 \le M$ , $N \le 25$ ) giving the dimensions of the grid. Then follows the description of the grid in M lines of N characters each. The character `#' will indicate a blocked square, all other squares are free. The starting location of the cyclist is marked by `S' and the target is marked by `T'. The input terminates with two zeros for M and N.

Output

For each test case in the input first print the test case number on a separate line as shown in the sample output. If the target location can be reached by the cyclist print the minimum amount of time (in seconds) required to reach it exactly in the format shown in the sample output, otherwise, print ``destination not reachable".

Print a blank line between two successive test cases.

Sample Input

1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
0 0

Sample Output

Case #1
destination not reachable
 
Case #2
minimum time = 49 sec

Miguel Revilla
2000-12-26
題意：一自行車的輪子被分成5個扇區，塗了5種不同顏色。自行車每1秒要麼騎到下一個格子，要麼左轉或者右轉90。。一開始自行車面向北，顏色為綠，到達目標格時，必須觸底顏色為綠，但朝向無限制。求到達目標格的最短時間。分析:自從做了網賽那道，第一次了解了bfs的狀態。。。這道題就是x,y坐標加上顏色，方向一共四個狀態。。。幾個注意的地方：一個是那個四個方向必須按照順時針順序從北開始，另一個是最後組數據不能有多余空格。。。。。

/**
 * @author neko01
 */
//#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define clr(a) memset(a,0,sizeof a)
#define clr1(a) memset(a,-1,sizeof a)
#define dbg(a) printf("%d\n",a)
typedef pair pp;
const double eps=1e-9;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
const LL inf=(((LL)1)<<61)+5;
char s[28][28];
bool vis[28][28][5][4];
struct node{
    int x,y,c,d,step;
    node(int x=0,int y=0,int c=0,int d=0,int step=0):x(x),y(y),c(c),d(d),step(step){}
};
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int n,m,sx,sy;
bool immap(int x,int y)
{
    return x>=0&&y>=0&&xq;
    vis[sx][sy][0][0]=true;
    q.push(node(sx,sy,0,0,0));
    while(!q.empty())
    {
        node cur=q.front();
        q.pop();
        int x=cur.x,y=cur.y;
        if(s[x][y]=='T'&&cur.c==0) return cur.step;
        for(int i=0;i<4;i++)
        {
            if(i==cur.d)
            {
                int xx=x+dir[i][0];
                int yy=y+dir[i][1];
                int nowc=(cur.c+1)%5;
                if(immap(xx,yy)&&!vis[xx][yy][nowc][i])
                {
                    vis[xx][yy][nowc][i]=true;
                    q.push(node(xx,yy,nowc,i,cur.step+1));
                }
            }
            if(i==(cur.d-1+4)%4||i==(cur.d+1)%4)
            {
                if(!vis[x][y][cur.c][i])
                {
                    vis[x][y][cur.c][i]=true;
                    q.push(node(x,y,cur.c,i,cur.step+1));
                }
            }
        }
    }
    return -1;
}
int main()
{
    int cnt=0;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        for(int i=0;i


















  Problem A: The Monocycle 





A monocycle is a cycle that runs on one wheel and the one we will be considering is a bit more special. It has a solid wheel colored with five different colors as shown in the figure:


The colored segments make equal angles (72^o) at the center. A monocyclist rides this cycle on an grid
 of square tiles. The tiles have such size that moving forward from the center of one tile to that of the next one makes the wheel rotate exactly 72^o around its own center. The effect is shown in the above figure. When the wheel is at the
 center of square 1, the mid-point of the periphery of its blue segment is in touch with the ground. But when the wheel moves forward to the center of the next square (square 2) the mid-point of its white segment touches the ground.


Some of the squares of the grid are blocked and hence the cyclist cannot move to them. The cyclist starts from some square and tries to move to a target square in minimum amount of time. From any square either he
 moves forward to the next square or he remains in the same square but turns 90^o left or right. Each of these actions requires exactly 1 second to execute. He always starts his ride facing north and with the mid-point of the green segment
 of his wheel touching the ground. In the target square, too, the green segment must be touching the ground but he does not care about the direction he will be facing.
Before he starts his ride, please help him find out whether the destination is reachable and if so the minimum amount of time he will require to reach it.

Input 
The input may contain multiple test cases.
The first line of each test case contains two integers M and N (, )
 giving the dimensions of the grid. Then follows the description of the grid in M lines of N characters each. The character `#' will indicate a blocked square, all other squares are free. The starting location of the cyclist is marked
 by `S' and the target is marked by `T'. The input terminates with two zeros for M and N.
Output 
For each test case in the input first print the test case number on a separate line as shown in the sample output. If the target location can be reached by the cyclist print the minimum amount of time (in seconds)
 required to reach it exactly in the format shown in the sample output, otherwise, print ``destination not reachable".
Print a blank line between two successive test cases.

Sample Input 
1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
0 0


Sample Output 
Case #1
destination not reachable
 
Case #2
minimum time = 49 sec






Miguel Revilla 

2000-12-26