题解

_k_e_v_i_n_ · 2021-12-04 19:22:09 · 题解

思路

输入。

cin>>n>>m;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='J')  b[i]=j,rmax=n-i+1;
            if(c=='J'&&a[i]==0) a[i]=j;
        }
    }

定义 rmax 记录出现的最高行数。

int rmax;

定义 now 表示横坐标。

int now;

定义 last 表示上一次吃苹果的纵坐标，也就是行数。

int last;

定义 ans 统计总步数。

int ans;

先统计第一行，第一行毫无疑问是从左走到右。

max(0,b[1]-1)

行数为偶数一定是从右走到左，于是乎写下这些代码。

if(i%2==0){
            if(b[i]==0)
                continue;

求出当前行最右边的位置和上一行最左边的位置。

ans+=abs(b[i]-now);

行数为奇数一定是从左走到右，做法跟偶数差不多。

if(b[i]==0) continue;
            ans+=i-last;
            last=i;
            ans+=abs(a[i]-now);
            ans+=abs(b[i]-a[i]);
            now=b[i];

思路汇总

一、输入，rmax记录出现的最高行数。

二、 now 表示横坐标。

三、 last 表示上一次吃苹果的纵坐标，也就是行数。

四、 ans 统计总步数，先统计第一行，第一行毫无疑问是从左走到右。

五、行数为偶数一定是从右走到左，行数为奇数一定是从左走到右。

六、行数为偶数的情况：往上走一步或多步，因为可能存在中间某几行都没有苹果的情况；求出当前行最右边的位置和上一行最左边的位置，把这一行都吃掉。

七、行数为奇数的情况跟行数为偶数的情况相似。

附上AC代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;
int n,m,rmax,a[10001],b[10001];
char c;
int main(){
    cin>>n>>m;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='J')  b[i]=j,rmax=n-i+1;  //rmax记录出现的最高行数
            if(c=='J'&&a[i]==0) a[i]=j;
        }
    }
    int now=max(1,b[1]);    // now 表示横坐标
    int last=1; // last 表示上一次吃苹果的纵坐标，也就是行数
    int ans=max(0,b[1]-1);  // ans 统计总步数，先统计第一行，第一行毫无疑问是从左走到右
    for(int i=2;i<=rmax;i++){
        if(i%2==0){ //行数为偶数一定是从右走到左
            if(b[i]==0) continue;
            ans+=i-last;    //往上走一步或多步，因为可能存在中间某几行都没有苹果的情况
            last=i;
            ans+=abs(b[i]-now); //求出当前行最右边的位置和上一行最左边的位置
            ans+=abs(b[i]-a[i]);    //把这一行都吃掉
            now=a[i];   //最终停留在这一行的位置，为下一行计算做准备 
        }else{  //行数为奇数一定是从左走到右
            if(b[i]==0) continue;
            ans+=i-last;
            last=i;
            ans+=abs(a[i]-now);
            ans+=abs(b[i]-a[i]);
            now=b[i];
        }
    }
    cout<<ans;
    return 0;
}

可以抄的代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;
int n,m,rmax,a[10001],b[10001];
char c;
int main(){
    cin>>n>>m;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='J')  b[i]=j,rmax=n-i+1;
            if(c=='J'&&a[i]==0) a[i]=j;
        }
    }
    int now=max(1,b[1]);
    int last=1;
    int ans=max(0,b[1]-1);
    for(int i=2;i<=rmax;i++){
        if(i%2==0){
            if(b[i]==0) continue;
            ans+=i-last;
            last=i;
            ans+=abs(b[i]-now);
            ans+=abs(b[i]-a[i]);
            now=a[i];
        }else{
            if(b[i]==0) continue;
            ans+=i-last;
            last=i;
            ans+=abs(a[i]-now);
            ans+=abs(b[i]-a[i]);
            now=b[i];
        }
    }
    cout<<ans;
    return 0;
}