Codeforces 115B

曾经终败给现在 2022-05-06 10:54 182阅读 0赞

题目地址：[http://codeforces.com/problemset/problem/115/B][http_codeforces.com_problemset_problem_115_B]

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

![70][]

记录左右两端杂草的位置，存在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);
    }

[http_codeforces.com_problemset_problem_115_B]: http://codeforces.com/problemset/problem/115/B
[70]: /images/20220506/dc2b0c7f1d97456f9246dc2030cef0cc.png