#include <iostream>
#include <fstream>
using namespace std;

#define SIZE 52
#define QUEUE_SIZE 10000

const int direct [][2] = {
    -1,0,
    0,1,
    1,0,
    0,-1};

bool map[SIZE][SIZE],visited[SIZE][SIZE][4];
int m,n;
int endx,endy;

struct Pos
{
    int x,y,dir;
    int cost;
};

Pos queue[QUEUE_SIZE];
int rear,front;

int push (int x,int y,int dir,int cost)
{
    // if success
    if (x == endx && y == endy)
    {
        return 1;
    } 
    if (visited[x][y][dir])
    {
        return 0;
    } 
    
    visited[x][y][dir] = true; 
        
    queue[front].x = x;
    queue[front].y = y;
    queue[front].dir = dir;
    queue[front].cost = cost;
    
    front++;
    front %= QUEUE_SIZE;
    
    return 0;
}    

void pop (int &x,int &y,int &dir,int &cost)
{
    x = queue[rear].x;
    y = queue[rear].y;
    dir = queue[rear].dir;
    cost = queue[rear].cost;
    
    rear ++;
    rear %= QUEUE_SIZE;
}    

int turn (int x,int y,int dir,int cost)
{
     if ( 1 == push (x,y,(dir + 3) % 4,cost + 1))
     {
         return 1;
     } 
     if ( 1 == push (x,y,(dir + 5) % 4 ,cost + 1))
     {
         return 1;
     }   
    
    return 0;
}  

int go (int x,int y,int dir,int cost)
{
    int i;
    
    for (i = 1;i <= 3;i++)
    {
        x += direct[dir][0];
        y += direct[dir][1];
        //printf ("p go  %d  %d\n",x,y);
        if (x < m && y < n && x >= 0 && y >= 0 && map[x][y])
        {
            //printf ("go  %d  %d\n",x,y);
            if (1 == push (x,y,dir,cost + 1))
            {
                return 1;
            }
        } 
        else
        {
            break;
        }       
    }
    
    return 0;
}      

int BFS (int begx,int begy,int direction)
{  
    int x,y,dir,cost,i;
    int tmp;
    
    if (1 == push (begx,begy,direction,0))
    {
        return 0;
    }    
    
    while (front != rear)
    {
        //printf ("get\n");
        pop (x,y,dir,cost);
        // 
        if (1 == turn (x,y,dir,cost))
        {
            return cost + 1;
        }    

        if (1 == go (x,y,dir,cost))
        {
             return cost + 1;
        }       
    }    
    
    return -1;
}    

void init ()
{
    int i,j;
    for (i = 0;i < m;i++)
    {
        for (j = 0; j < n;j++)
        {
            map[i][j] = true;
            visited[i][j][0] = visited[i][j][1] =
            visited[i][j][2] = visited[i][j][2] = false;
        }    
    }    
    front = rear = 0;
}    


int main ()
{
    #ifndef ONLINE_JUDGE
    freopen ("Robot.txt","r",stdin);
    #endif
    
    int m1,n1,tmp;
    int i,j;
    int begx,begy,dir;
    char buff[10];
    
    while (EOF != scanf ("%d%d",&m1,&n1)
    && !( 0 == m1 && n1 == 0))
    {
        m = m1 + 1;
        n = n1 + 1;
        init ();
        for (i = 0; i < m1; i++)
        {
            for (j = 0; j < n1; j++)
            {
                scanf ("%d",&tmp);
                if (tmp == 1)
                {
                    map[i + 1][j + 1] = map [i][j + 1] =
                    map[i][j] = map[i + 1][j] = false;
                }    
            }    
        }
        
        scanf ("%d%d%d%d%s",&begx,&begy,&endx,&endy,buff);
        switch (buff[0])
        {
            case 's' : dir = 2;break;
            case 'n' : dir = 0;break;
            case 'w' : dir = 3;break;
            case 'e' : dir = 1;break;
        }
               
        printf ("%d\n",BFS (begx,begy,dir)); 
    }    
    
    #ifndef ONLINE_JUDGE
    printf ("end\n");
    while (true) {}
    #endif
    
    return 0;
}    

• Re:谁能帮忙看下这个程序为什么WA了，谢谢 (4133) kansas 2006-05-31 17:41:37