Codeforces 115B-蒲公英云

Codeforces 115B

题目地址：http://codeforces.com/problemset/problem/115/B

心里苦，越想越复杂，把空行的可能性考虑的太多了…然后发现其实就只需要一开始想的那些就够了…

记录左右两端杂草的位置，存在left和right数组里，因为向下走的时候方向会变，所以考虑奇偶行，k标记上一个结点。

nn用来记录走到第几行，因为可能有

GGGW

GGGG

这种数据，只要走一行就行了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int main() 
{    
    int n,nn,m,i,j,s=0;
    char a[200][200]; 
    int left[200],right[200];
    memset(left,inf,sizeof left);
    memset(right,-inf,sizeof right);
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%s",a[i]+1);
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j]=='W')
            {
                left[i]=j;
                break;
            }
        }
        for(j=m;j>=1;j--)
        {
            if(a[i][j]=='W')
            {
                right[i]=j;
                break;
            }
        }
    } 
    //for(i=1;i<=n;i++)
    //printf("%d %d\n",left[i],right[i]);
    nn=1;
    int k=1;
    for(i=1;i<=n;i++)
    {
        if(left[i]<=right[i])
        {
            nn=i;
            if(i%2==1)
            {
                s+=abs(k-left[i])+right[i]-left[i];
                k=right[i];
            }
            else
            {
                s+=abs(k-right[i])+right[i]-left[i];
                k=left[i];
            }
        }
    }        
    printf("%d\n",s+nn-1);
}