某ACM题无限RuntimeError，求解救解决方法

某ACM题无限RuntimeError，求解救

Description

有一块 n × m的长方形(n,m分别表示行列)土地，上面只长有杂草和小麦。对于n × m个格子，每个格子只能长小麦或是杂草。例如下图4×5的长方形土地(空格表示小麦)

农民yanmie有一台剪草机，现在他想把所有的杂草给除掉。他从左上角的坐标（1,1）面对右边开始。每一步的走法具体如下：
可以朝yamie的面对的方向走一步。
•如果yanmie是朝右，可以从当前位置(r,c)走到(r,c+1);(如下图)

•如果yanmie是朝左，可以从当前位置(r,c)走到(r,c-1);(如下图)

可以向下走一步，也就是从当前位置(r,c)走到(r+1,c)。但每次向下走一步，yamie面对的方向就会变反，具体如下。
•如果之前是朝向右边，向下走一步就会变为朝向左。（如下图）

•如果之前是朝向左边的，向下走一步就会变位朝向右。（如下图）

现在农民yamie想知道走最少的步数把那些杂草铲除。注意：yamie不能走出这个长方形。

Input

第一行包含一个数T,表示有T组样例。每组样例后有两个整数n和m（1 ≤ n, m ≤ 150），分别表示行和列。然后是n行m列的字符，"G"表示小麦，"W"表示杂草。输入保证一开始左上角坐标为(1,1)的格子不是杂草。

Output

输出一个数 - 最少铲除杂草需要走的步数。

Sample Input

1
4 5
GWGGW
GGWGG
GWGGG
WGGGG
Sample Output

11
Hint

C/C++ code

# include<stdio.h>
# include<string.h>

char map[200][200];
int n,m,l,num,d;   //l为W的总数，其余下同
int rear,front;

struct node
{
    int p,d,val,num;  //p为方向(1为右，-1为左，d为走了的步数，num为遇到W的个数，val是m*x+y的值)
}queue[100000];

void bfs()
{
    int u,x,y,p;  
    queue[rear].val = 0;    //（0，0）入队，方向为右
    queue[rear].p = 1;
    queue[rear].num = 0;
    queue[rear++].d = 0;
    while(front<rear)
    {
        u = queue[front].val;     //出队
        p = queue[front].p;
        d = queue[front].d;
        num = queue[front++].num;
        x = u/m;
        y = u%m;
        if(num >= l) break;    //清除所有草，则退出    
        if(y+1<=m-1 && p>0)   //右走一步，方向为正，如果可行则入队
        {
            if(map[x][y+1] == 'W')queue[rear].num = num+1;
            else queue[rear].num = num;
            queue[rear].val = m*x+y+1;
            queue[rear].d = d+1;
            queue[rear++].p = 1;
        }
        if(y-1>=0 && p<0)    //左走一步
        {
            if(map[x][y-1] == 'W')queue[rear].num = num+1;
            else queue[rear].num = num;
            queue[rear].val = m*x+y-1;
            queue[rear].d = d+1;
            queue[rear++].p = -1;
        }
        if(x+1<=n-1 && p>0)   //下走一步方向为正
        {
            if(map[x+1][y] == 'W')queue[rear].num = num+1;
            else queue[rear].num = num;
            queue[rear].val = m*(x+1)+y;
            queue[rear].d = d+1;
            queue[rear++].p = -1;
        }
        else if(x+1<=n-1 && p<0)  //下走一步方向为负
        {
            if(map[x+1][y] == 'W')queue[rear].num = num+1;
            else queue[rear].num = num;
            queue[rear].val = m*(x+1)+y;
            queue[rear].d = d+1;
            queue[rear++].p = 1;
        }
    }
}

int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        rear = front = l = d = 0;
        memset(queue,0,sizeof(queue[0]));
        for(i=0;i<n;i++) 
        {
            scanf("%s",map[i]);
            for(j=0;j<m;j++)
            {
                if(map[i][j] == 'W') l++;
            }
        }
        bfs();
        printf("%d\n",d);
    }
    return 0;
}

------解决方案--------------------
gcc4.2表示执行正确，没runtime
------解决方案--------------------
这个真没看出来。。。

某ACM题无限RuntimeError，求解救解决方法

相关推荐