蟻本p153 座標圧縮の関数がうまく機能しない

Question

前提・実現したいこと

以下の問題を解いているのですが、次の座標圧縮の関数を用いても領域が圧縮されません。具体的にどこが誤っているのかご指摘いただけると幸いです。よろしくお願いします。

問題
W * Hの格子状にN本の垂直または水平な幅1の直線が引かれています。格子は線によって何個の領域に分かれているか。
入力サンプル
W = 10, H = 10, N = 5
X1 = {1, 1, 4, 9, 10}
X2 = {6, 10, 4, 9, 10}
Y1 = {4, 8, 1, 1, 6}
Y2 = {4, 8 10, 5, 10}

X1[i], X2[i], Y1[i], Y2[i]はi番目の直線の２つの端点の座標((X1[i], Y1[i]), (X2[i], Y2[i]))

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int INF = 1e9;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <typename Type> inline string toString(const Type &a){ostringstream oss; oss << a; return oss.str();}

int W, H, N;


int compress(vector<int> &x1, vector<int> &x2, int w){
    vector<int> xs;
    for(int i = 0; i < N; ++i){
        for(int d= -1; d <= 1; ++d){
            int tx1 = x1[i] + d, tx2 = x2[i] + d;
            if(tx1 >= 1 && tx1 <= w){
                xs.push_back(tx1);
            }
            if(tx2 >= 1 && tx2 <= w){
                xs.push_back(tx2);
            }
        }
    }
    sort(xs.begin(), xs.end());
    auto it = unique(xs.begin(), xs.end());
    xs.erase(it, xs.end());
    for(int i = 0; i < N; ++i){
        x1[i] = lower_bound(xs.begin(), xs.end(), x1[i]) - xs.begin();
        x2[i] = lower_bound(xs.begin(), xs.end(), x2[i]) - xs.begin();
    }
    return xs.size();
}

vector<vector<int>> tile;
vector<int> X1, X2, Y1, Y2;
int dx[4] = {1, 0 , -1, 0}, dy[4] = {0, 1, 0, -1};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> W >> H >> N;
    X1.resize(N);
    X2.resize(N);
    Y1.resize(N);
    Y2.resize(N);
    for(int i = 0; i < N; ++i) cin >> X1[i];
    for(int i = 0; i < N; ++i) cin >> X2[i];
    for(int i = 0; i < N; ++i) cin >> Y1[i];
    for(int i = 0; i < N; ++i) cin >> Y2[i];
    W = compress(X1, X2, W); H = compress(Y1, Y2, H);
    tile.assign(H, vector<int>(W, 0));
    for(int i = 0; i < N; ++i){
        for(int y = Y1[i]; y <= Y2[i]; ++y){
            for(int x = X1[i]; x <= X2[i]; ++x){
                tile[y][x] = 1;
            }
        }
    }

    int ans = 0;
    for(int y = 0; y < H; ++y){
        for(int x = 0; x < W; ++x){
            if(tile[y][x]) continue;
            queue<pair<int, int>> que;
            que.push(make_pair(x, y));
            tile[y][x] = 1;
            ans++;
            while(!que.empty()){
                pair<int, int> p = que.front(); que.pop();
                for(int i = 0; i < 4; ++i){
                    int nx = p.first + dx[i], ny = p.second = p.second + dy[i];
                    if(nx >= 0 && nx < W && ny >= 0 && ny < H){
                        if(tile[ny][nx]) continue;
                        else{
                            que.push(make_pair(nx,ny));
                            tile[ny][nx] = 1;
                        }
                    }
                }
            }
            
        }
    }
    cout << ans << endl;

}

Comments

[yudedako67]

うまくいっていないと考えているのはなぜですか?
例えば「～という結果になるはずだが、~という結果になる」

[rdld036]

恐らく問題があるのは全探索の方でしょうか。今回のサンプルだと、蟻本では答えが6になるのにこのコードでやると、forループで座標(4,0)を起点に幅全探索をした時座標(4,4,)が探索されず残り、その分一つ余計に領域をカウントすることにより7になります。ただ、なぜこの点だけ飛ばされるのか教えていただけますか

Answer 1

int nx = p.first + dx[i], ny = p.second = p.second + dy[i];

Why do you change p.second ?

Comments

[fana]

You wrote the code, and the result was wrong.
If so, you need to debug.
Why don't ?

[rdld036]

That's a typo...Thank you for letting me know!

[rdld036]

I debugged it but it didn't display any error messages

[fana]

ああ，もう，めんどくさいから日本語で書くけどもさ，

結果値がおかしい　ってときにエラーメッセージなんか出るわけないのよね．

探索処理がおかしいと思うなら，探索している座標のチェックくらいするっしょ，ふつーは．
想定した探索順はご自身で知っているんだから，それと実際の探索座標の順序を見比べるとかすれば
こんな単純ミスを見つけるのには５分もいらないハズ．

何か動きがおかしい，っていうなら，「ちゃんと想定通りに動いてるんか？」っていうのを見る．
何を見れば何を確認できるのか？　っていう視点に立って，見るべきものを見る．

[fana]

> 座標(4,4)

が1にならん，っていう異常をせっかく発見したんだから，
「何でそうなるのか？」という要因も考えようよ．

1にする処理は queue に突っ込む処理と同じ個所にあるんだから，
原因は「queueに突っ込むべき座標が異常になってるのでは？」というところまでは推測できる．
↓
そしたら，「座標をqueueに突っ込む処理」のあたりで実際には何が起こってるのか？　を見る．

事件の様子から　推理して，証拠を集めて，犯人を突き止める．
事件を見つけるだけじゃダメだ．

[fana]

あと，全然関係ないけども，今回のコードは

int nx = p.first + dx[i];
int ny = p.second = p.second + dy[i];

って２行で書いてれば，見た目から瞬間的に間違いに気づけるものだったと思う．
（一方だけが異常に長い）

[rdld036]

書式についてもこれから気をつけたいと思います。大切なことを色々教えてくださり誠にありがとうございます。

[fana]

わざわざこの手のパズルみたいな問題に取り組んでるのは　考えることを楽しんでるんだろう，と思うので，
デバッグも同じように楽しめばいいんじゃないかな．
そしたら一粒で二度おいしい．