ABC109 D - Make Them Even

勉強記録

今日はABC109 Dを解きました。 割とスムーズに解放が思いついたけど、実装が面倒だった。

問題

atcoder.jp

考えたこと

だいたいつぶやきのまんまです。 ジグザグに見ていかなきゃなので、添字を動かすのが面倒だった。 あとは操作履歴をバッファにプールしてくところ？

解答

見ているマスの移動が操作に対応するか？を見るために、移動中フラグを作りました。

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)

int main(){

    long long h,w;
    cin >> h >> w;

    vector<vector<long long>> m(h,vector<long long>(w));
    long long cnt = 0;

    rep(i,h)
    rep(j,w){
        long long buf;
        cin >> buf;
        m[i][j] = buf & 0x01;
        if(m[i][j]) cnt++;
    }

    if(cnt & 0x01) cnt--;

    bool mv_flg = false;
    vector<pair<pair<long long,long long>, pair<long long,long long>>> ans;

    long long i = 0;
    long long j = 0;
    while(cnt > 0){
        // chk
        if(m[i][j] && !mv_flg){
            mv_flg = true;
        } else if(m[i][j] && mv_flg) {
            mv_flg = false;
            cnt--;
        }

        // move
        pair<long long,long long> bef;
        bef = make_pair(i,j);

        if(i & 0x01){
            if(j > 0){
                j--;
            } else {
                i++;
            }
        } else {
            if(j != w - 1){
                j++;
            } else {
                i++;
            }
        }

        if(mv_flg){
            pair<long long,long long> aft;
            aft = make_pair(i,j);
            ans.emplace_back(make_pair(bef,aft));
        }

        // break chk
        if(i == h - 1){
            if(h & 0x01){
                if(j == w - 1){
                    break;
                }
            } else {
                if (j == 0){
                    break;
                }
            }
        }
    }

    // output
    cout << ans.size() << endl;
    rep(i,ans.size()){
        cout << ans[i].first.first + 1 << " " << ans[i].first.second + 1 << " " << ans[i].second.first + 1 << " " << ans[i].second.second + 1 << endl;
    }


    return 0;
}

感想

解説見たら経路を予め作っていましたね。そういうのでもいいのか…。