题目大意
简单来讲就是从(1,1)向左或右或下走,经过所有草坪的最短路程
思路:
由于在第一行只能向右走,那么我们就知道,在单数行和双数行分别是向右走和向左走,那么我们在单数行就只需要统计最右边的数,在双数行就只要统计最左边的数,我们储存了"上"一行的位置,那么如果是在单数行,就扫到其最右端,相反,如果是双数行,就扫到其最左端
特判情况
如果我们扫了一行后,发现其后面没有草了,这个时候我们就要停止继续向下寻找了
如何实现呢?
按照我的思路
我们用一个bool数组来储存每一行是否有草,由于这个行走是单向的只能向下走,所以特判的情况只在最后几行
我们用while(b[len]==false&&len>0) len--来计算
这样我们循环是就只要循环到len行就可以了
我们用一个ans来统计最后的步数
这道题目就讲完啦
#include<bits/stdc++.h> using namespace std; int n,m; int a[200][3]; bool b[200]; int c[200]; int star=0,sum=0,ans; int main() { cin>>n>>m; char h; for(int i=1;i<=n+1;i++) { b[i]=false; a[i][1]=1; a[i][2]=m; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>h; if(h=='W') b[i]=true; if(h=='W'&&j>a[i][1]) a[i][1]=j; if(h=='W'&&j<a[i][2]) a[i][2]=j; } } star=1; sum=0; ans=0; int len=n; while(b[len]==false&&len>0) len--; for(int i=1;i<=len-1;i++) { ++ans; if(i%2==1) { while(star<a[i][1] || star<a[i+1][1]) ++star,++ans; // cout<<star<<" "<<ans<<endl; continue; } while(star>a[i][2] || star>a[i+1][2]) --star,++ans; //cout<<star<<" "<<ans<<endl; } // cout<<len<<endl; if(len==0) { cout<<0; return 0; } if(len%2==1) while (star<a[len][1]) ++star,++ans; else while(star>a[len][2]) --star,++ans; cout<<ans; return 0; } /* 思考一下怎么特判..... 如果有单数行没有的话,并且在我现在位置的左边 我们就要在空的那一行向左走到相应位置 如果空了双数行,我就直接穿过当做不存在 我们还要记录"1"的个数,方便随时结束我们的寻找.... 大概是这样子的吧... */