P7660 [COCI2014-2015#5] ZMIJA

_YyD_ · 2021-07-18 07:37:22 · 题解

题目大意：

一个n\times m(n,m\leq1000)的格子中有若干金币，从左下角出发，每一步可以进行如下操作：

　　　　1.向当前方向前进一格；

　　　　2.向上移动一步，并调转当前方向。

一开始的方向是向右，到达一个格子时自动收集当前位置的金币，移动过程中不能离开网格图。

问收集完所有金币至少需要多少步？

思路：

贪心。

首先记录下每一行最左/最右的金币的位置，每次贪心地取完这一行的所有金币，

然后判断上一行最左/最右的金币是否在当前方向上，

如果是，就先往前走到那个位置上，然后再上去，否则就直接上去。

代码：

#include<bits/stdc++.h>
#define _ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read() {
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
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 mp[N][N];
int main() {
    const int n=read(),m=read();
    rep(i,1,n) {
        rep(j,1,m) {
            mp[i][j]=getblock();
            if(mp[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(mp[x][y]) {
            cnt[x]--;
            sum--;
        }
        while(cnt[x]) {
            ans++;
            y+=d;
            if(mp[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++;
    }
    cout<<ans;
    return 0;
}

注明：

思路来自 skylee。