[COCI2015]ZMIJA

题目大意：
　　一个$n imes m(n,mleq1000)$的格子中有若干金币，从左下角出发，每一步可以进行如下操作：
　　　　1.向当前方向前进一格；
　　　　2.向上移动一步，并调转当前方向。
　　一开始的方向是向右，到达一个格子时自动收集当前位置的金币，移动过程中不能离开网格图。
　　问收集完所有金币至少需要多少步？

思路：
　　贪心。
　　首先记录下每一行最左/最右的金币的位置，每次贪心地取完这一行的所有金币，
　　然后判断上一行最左/最右的金币是否在当前方向上，
　　如果是，就先往前走到那个位置上，然后再上去，否则就直接上去。

#include<cstdio>
#include<cctype>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
inline bool isblock(const char &ch) {
    return ch=='.'||ch=='J'||ch=='Z';
}
inline bool getblock() {
    register char ch;
    while(!isblock(ch=getchar()));
    return ch=='J';
}
inline int sign(const int &x) {
    if(x>0) return 1;
    if(x<0) return -1;
    return 0;
}
const int N=1001;
int cnt[N],pos[N][2],sum;
bool map[N][N];
int main() {
    const int n=getint(),m=getint();
    for(register int i=1;i<=n;i++) {
        for(register int j=1;j<=m;j++) {
            map[i][j]=getblock();
            if(map[i][j]) {
                if(!pos[i][0]) pos[i][0]=j;
                pos[i][1]=j;
                cnt[i]++;
                sum++;
            }
        }
    }
    int ans=0;
    for(register int x=n,y=1,d=1;;x--,d=-d) {
        if(map[x][y]) {
            cnt[x]--;
            sum--;
        }
        while(cnt[x]) {
            ans++;
            y+=d;
            if(map[x][y]) {
                cnt[x]--;
                sum--;
            }
        }
        if(!sum) break;
        while(pos[x-1][(bool)~d]&&sign(pos[x-1][(bool)~d]-y)==d) {
            y+=d;
            ans++;
        }
        ans++;
    }
    printf("%d
",ans);
    return 0;
}