programming.in.th · ข้อ 2014

กำแพงกับน้ำท่วม: ประโยคว่าพังทีละชั่วโมง แปลเป็นระยะทางบนกราฟได้ตรง ๆ

ข้อที่ประโยคเฉลยสั้นที่สุดในคลังนี้ คือกำแพงรอดเมื่อสองข้างท่วมพร้อมกัน ที่เหลือคือ BFS ธรรมดา บทนี้ให้ทั้งเวอร์ชันตารางที่ได้ 40 คะแนนและใช้เป็นตัวตรวจสอบ กับเวอร์ชันเต็มที่ต้องสร้างพื้นที่ของผังเอง

★★★★★ geometrybfsdfs อ่าน 14 นาที 7 กันยายน 2026

โจทย์ · น้ำท่วมทีละชั้น กำแพงพังทีละชั้น

ปี 1964 เกิดน้ำท่วมใหญ่ที่เมืองซาเกร็บ โจทย์นี้ให้แบบจำลองของเมืองก่อนน้ำท่วม เป็นจุด N จุดบนระนาบ กับกำแพง W เส้น แต่ละเส้นเชื่อมจุดสองจุดและ ไม่ผ่านจุดอื่นเลย กำแพงทุกเส้นขนานกับแกน และไม่มีเส้นไหนตัดหรือทับกัน (แตะกันได้แค่ที่ปลาย)

ตอนเริ่มต้นทุกที่แห้ง แล้วน้ำท่วมบริเวณนอกสุดทันที หลังจากนั้นทุก ๆ หนึ่งชั่วโมง กำแพงทุกเส้นที่ข้างหนึ่งเป็นน้ำ อีกข้างเป็นอากาศ จะพังลง แล้วน้ำก็ไหลเข้าไปในพื้นที่ที่เพิ่งเปิด ทำซ้ำจนน้ำท่วมทั่ว งานของเราคือบอกว่ากำแพงเส้นไหนบ้างที่ยังยืนอยู่

อินพุต / ขอบเขต / เอาต์พุต

อินพุต: บรรทัดแรกคือ N ตามด้วย N บรรทัดของพิกัดจุด จากนั้นคือ W และอีก W บรรทัดของหมายเลขจุดสองจุดที่กำแพงเส้นนั้นเชื่อม
ขอบเขต: 2 ≤ N ≤ 100,000, 1 ≤ W ≤ 2N พิกัดอยู่ระหว่าง 0 ถึง 1,000,000 เวลา 2 วินาที หน่วยความจำ 32 เมกะไบต์
เอาต์พุต: บรรทัดแรกคือจำนวนกำแพงที่ยังอยู่ จากนั้นคือหมายเลขของกำแพงเหล่านั้น เรียงยังไงก็ได้
ให้คะแนน: มี 40 คะแนนสำหรับชุดทดสอบที่พิกัดทุกตัวไม่เกิน 500 และอีก 15 คะแนนที่จำนวนจุดไม่เกิน 500

EXAMPLE
Input	Output
15 1 1 8 1 4 2 7 2 2 3 4 3 6 3 2 5 4 5 6 5 4 6 7 6 1 8 4 8 8 8 17 1 2 2 15 15 14 14 13 13 1 14 11 11 12 12 4 4 3 3 6 6 5 5 8 8 9 9 11 9 10 10 7 7 6	4 6 15 16 17

ใบ้

กำแพงพังเมื่อข้างหนึ่งเปียก อีกข้างแห้ง ลองกลับด้านประโยคนี้ดู กำแพงจะไม่พัง เมื่อไร

ถ้าเราหาได้ว่าแต่ละบริเวณน้ำถึงเมื่อชั่วโมงที่เท่าไร คำถามทั้งข้อจะเหลืออะไร

ลองเอง · ทายว่ากำแพงเส้นไหนจะรอด

ผังนี้มีห้องปิดหนึ่งห้อง กับกำแพงเดี่ยว ๆ ที่ไม่ได้ล้อมอะไรเลย

กดเลือกกำแพงที่คิดว่าจะรอด แล้วกดตรวจ กำแพงที่ไม่ได้เลือกคือกำแพงที่คิดว่าจะพัง

เลือกไว้ 0 เส้น จากทั้งหมด 0 เส้น

น้ำเริ่มจากทะเลรอบนอก และทะลุกำแพงได้ชั่วโมงละหนึ่งชั้น

ถ้าทายพลาดบ่อย ลองเปลี่ยนคำถามในหัวจาก "กำแพงนี้แข็งแรงไหม" เป็น "น้ำสองข้างของกำแพงนี้มาถึงพร้อมกันหรือเปล่า"

เฉลย · กำแพงรอดก็ต่อเมื่อสองข้างเปียกพร้อมกัน

ที่มาของแนวคิดนี้ และจุดที่ผมสะดุด

ลำดับจริงคือผมไม่ได้เริ่มจากกราฟระนาบเลย ผมเริ่มจากเวอร์ชันง่ายที่สุดคือมองผังเป็นตารางช่องละหนึ่งหน่วย แล้วปล่อยน้ำท่วมทีละชั้น เวอร์ชันนั้นเขียนง่าย ตอบตัวอย่างในโจทย์ถูก และกลายเป็นเฉลยชุดทดสอบย่อย 40 คะแนน พอมันเดินได้ ผมถึงกลับไปอ่านประโยคที่มันใช้ตัดสินใจ คือ "กำแพงรอดเมื่อสองข้างท่วมพร้อมกัน" แล้วเห็นว่าประโยคเดียวกันนี้ไม่ได้ต้องการช่องเลย มันต้องการแค่คำว่าสองข้าง ซึ่งหน้าของกราฟระนาบก็มีให้เหมือนกัน

จุดที่ผมสะดุดอยู่นานคือเรื่องราคา กำแพงหนึ่งเส้นพังทั้งเส้นพร้อมกัน ไม่ได้พังทีละช่อง ตอนนั้นผมนึกว่าการคิดราคาทีละช่องจะทำให้ตอบผิด สิ่งที่ทำให้กลับมามั่นใจคือ ช่องที่อยู่ในพื้นที่ผืนเดียวกันเชื่อมถึงกันด้วยการเดินที่มีราคาศูนย์ ค่าที่คำนวณได้ของทุกช่องในผืนเดียวกันจึง เท่ากันเสมอโดยอัตโนมัติ การคิดทีละช่องกับการคิดทีละผืนจึงให้เลขเดียวกัน

บทเรียนที่ยกไปข้ออื่นได้คือ เขียนเวอร์ชันหยาบที่ถูกให้เดินได้ก่อน แล้วอ่านว่ามันใช้ประโยคไหนตัดสินใจ ประโยคนั้นมักไม่ผูกกับโครงสร้างหยาบ ๆ ที่เราใช้ และนั่นคือทางไปเวอร์ชันเต็ม

กำแพงเส้นหนึ่งกั้นพื้นที่สองผืน ให้ dist ของผืนหนึ่งคือชั่วโมงที่น้ำท่วมถึงผืนนั้น ถ้าสองผืนมีค่าต่างกัน ก็ต้องเคยมีช่วงเวลาที่ผืนหนึ่งเป็นน้ำ อีกผืนยังเป็นอากาศ กำแพงจึงพัง แต่ถ้าสองผืนท่วมพร้อมกันเป๊ะ กำแพงเส้นนั้นไม่เคยรับแรงต่างข้างเลยสักชั่วโมง

กำแพงยังยืนอยู่ ก็ต่อเมื่อพื้นที่สองข้างของมันมีชั่วโมงที่น้ำท่วมถึงเท่ากันพอดี

แล้ว dist หาได้ยังไง มองว่าการเดินจากพื้นที่หนึ่งไปพื้นที่ที่ติดกันต้องข้ามกำแพงหนึ่งเส้น ซึ่งราคาหนึ่งชั่วโมง เริ่มจากพื้นที่นอกสุดที่ dist เป็นศูนย์ แล้วค้นตามความกว้าง ออกไป นี่คือ BFS ธรรมดา ไม่ต้องใช้อะไรหรูกว่านั้นเลย

หัวใจของทั้งข้อ

// dist[f] = ชั่วโมงที่น้ำท่วมถึงพื้นที่ f  หาได้ด้วย BFS ธรรมดาจากพื้นที่นอกสุด
// กำแพงเส้นหนึ่งกั้นพื้นที่สองผืน ถ้าน้ำถึงสองผืนนั้นคนละชั่วโมง แปลว่าเคยมีจังหวะที่
// ข้างหนึ่งเป็นน้ำอีกข้างเป็นอากาศ กำแพงจึงพัง  ถ้าถึงพร้อมกัน กำแพงไม่เคยรับแรงต่างข้าง
for (int e = 0; e < w; e++) {
    int a = find(heFace[2 * e]), b = find(heFace[2 * e + 1]);
    if (dist[a] == dist[b]) ans.push_back(e + 1);
}

กำแพงเส้นซ้ายกั้นพื้นที่ที่น้ำถึงคนละชั่วโมง จึงเคยมีช่วงที่ข้างหนึ่งเป็นน้ำอีกข้างเป็นอากาศ มันจึงพัง ส่วนเส้นขวากั้นพื้นที่ที่น้ำถึงพร้อมกัน มันจึงยืนอยู่ได้ตลอด (วาดประกอบโดยผู้เขียน)

ตารางชั่วโมงที่น้ำถึง ของตัวอย่างในโจทย์

ขั้น 0

กดถัดไปเพื่อตรวจกำแพงทีละเส้น

กำแพงทั้ง 17 เส้น
เส้นที่	เชื่อมจุด	น้ำถึงฝั่งหนึ่ง	น้ำถึงอีกฝั่ง	ผล
1	`1 ถึง 2`	0	1	พัง
2	`2 ถึง 15`	1	0	พัง
3	`15 ถึง 14`	1	0	พัง
4	`14 ถึง 13`	1	0	พัง
5	`13 ถึง 1`	0	1	พัง
6	`14 ถึง 11`	1	1	รอด
7	`11 ถึง 12`	2	1	พัง
8	`12 ถึง 4`	2	1	พัง
9	`4 ถึง 3`	1	2	พัง
10	`3 ถึง 6`	1	2	พัง
11	`6 ถึง 5`	1	2	พัง
12	`5 ถึง 8`	1	2	พัง
13	`8 ถึง 9`	2	1	พัง
14	`9 ถึง 11`	1	2	พัง
15	`9 ถึง 10`	2	2	รอด
16	`10 ถึง 7`	2	2	รอด
17	`7 ถึง 6`	2	2	รอด

กำแพงที่รอดมี 4 เส้น คือเส้นที่ 6, 15, 16, 17 ตรงกับคำตอบในโจทย์ ตัวเลขทุกตัวมาจากการเดินน้ำจริงบนตารางในหน้านี้ ไม่ได้พิมพ์มือ น้ำใช้เวลาท่วมทั่วทั้งเมืองนี้ 2 ชั่วโมง

สังเกตว่าเส้นที่ 6 กับ 15 กับ 16 กับ 17 ล้วนเป็นเส้นที่ทั้งสองข้างเป็นพื้นที่ผืนเดียวกัน หรือเป็นผืนที่น้ำเดินไปถึงด้วยจำนวนกำแพงเท่ากันพอดีทั้งสองทาง

อีกมุมหนึ่ง: มองเป็นตารางช่องละหนึ่งหน่วย (ชุดทดสอบย่อย 40 คะแนน)

ชุดทดสอบย่อยให้พิกัดไม่เกิน 500 ซึ่งเป็นคำเชิญให้ทำอะไรที่ตรงไปตรงมามาก แบ่งระนาบเป็นช่องละหนึ่งหน่วย กำแพงกลายเป็นเส้นขอบระหว่างช่อง แล้วเดินน้ำบนช่อง โดยการเดินข้ามขอบที่ไม่มีกำแพงราคาศูนย์ และข้ามขอบที่มีกำแพงราคาหนึ่ง

การเดินที่มีราคาแค่ศูนย์กับหนึ่งใช้ BFS แบบสองแถว ได้ คือใช้คิวสองหัว เจอราคาศูนย์ก็ยัดหน้าคิว เจอราคาหนึ่งก็ต่อท้าย ได้ผลเหมือน Dijkstra แต่เร็วเท่า BFS

ดูโค้ดของชุดทดสอบย่อย

flood_grid.cpp

// เฉลยชุดทดสอบย่อย พิกัดไม่เกิน 500  มองพื้นที่เป็นตารางช่องละหนึ่งหน่วย
#include <bits/stdc++.h>
using namespace std;
int G;
static inline int cid(int i,int j){ return i*G+j; }
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<int> X(n+1),Y(n+1); int mx=0;
    for(int i=1;i<=n;i++){ scanf("%d %d",&X[i],&Y[i]); X[i]++; Y[i]++; mx=max(mx,max(X[i],Y[i])); }
    int w; scanf("%d",&w);
    vector<int> A(w+1),B(w+1);
    for(int i=1;i<=w;i++) scanf("%d %d",&A[i],&B[i]);
    G=mx+2;
    vector<char> blkH((size_t)G*G,0), blkV((size_t)G*G,0);   // blkH[i][j] = กำแพงระหว่างช่อง (i,j-1) กับ (i,j)
    for(int e=1;e<=w;e++){
        int a=A[e],b=B[e];
        if(Y[a]==Y[b]){ int yy=Y[a],x1=min(X[a],X[b]),x2=max(X[a],X[b]);
            for(int i=x1;i<x2;i++) blkH[cid(i,yy)]=1; }
        else { int xx=X[a],y1=min(Y[a],Y[b]),y2=max(Y[a],Y[b]);
            for(int j=y1;j<y2;j++) blkV[cid(xx,j)]=1; }
    }
    const int INF=INT_MAX;
    vector<int> dist((size_t)G*G,INF);
    deque<int> dq; dist[cid(0,0)]=0; dq.push_back(cid(0,0));
    while(!dq.empty()){
        int u=dq.front(); dq.pop_front();
        int i=u/G,j=u%G,d=dist[u];
        auto go=[&](int ni,int nj,int cost){
            if(ni<0||nj<0||ni>=G||nj>=G) return;
            int v=cid(ni,nj); if(d+cost<dist[v]){ dist[v]=d+cost; if(cost) dq.push_back(v); else dq.push_front(v); }
        };
        go(i,j+1, blkH[cid(i,j+1)]);
        go(i,j-1, blkH[cid(i,j)]);
        go(i+1,j, blkV[cid(i+1,j)]);
        go(i-1,j, blkV[cid(i,j)]);
    }
    vector<int> ans;
    for(int e=1;e<=w;e++){
        int a=A[e],b=B[e]; bool alive;
        if(Y[a]==Y[b]){ int yy=Y[a],x1=min(X[a],X[b]); alive = dist[cid(x1,yy-1)]==dist[cid(x1,yy)]; }
        else { int xx=X[a],y1=min(Y[a],Y[b]); alive = dist[cid(xx-1,y1)]==dist[cid(xx,y1)]; }
        if(alive) ans.push_back(e);
    }
    printf("%d\n",(int)ans.size());
    for(int e:ans) printf("%d\n",e);
}

โน้ต

มีจุดหนึ่งที่ดูเหมือนจะผิดแต่ไม่ผิด กำแพงพังทั้งเส้นพร้อมกัน ไม่ใช่พังทีละช่อง แล้วทำไมการคิดราคาทีละช่องถึงยังถูก

เพราะช่องที่อยู่ในพื้นที่ผืนเดียวกันเชื่อมถึงกันด้วยการเดินราคาศูนย์ทั้งหมด มันจึงได้ค่าเท่ากันเสมออยู่แล้ว และเพราะโจทย์รับประกันว่ากำแพงไม่ตัดกันและไม่มีจุดอื่นอยู่กลางเส้น กำแพงหนึ่งเส้นจึงกั้นพื้นที่ สองผืนเดิมตลอดความยาวของมัน ทุกช่องคู่ตลอดเส้นจึงตัดสินเหมือนกันหมด

ท่านี้ได้ 40 คะแนนและตายทันทีที่พิกัดขึ้นเป็นล้าน แต่มันมีค่ามากกว่านั้น เพราะมันเป็นตัวตรวจสอบ ให้เวอร์ชันเต็ม ผมสุ่มผังกำแพงบนตารางเล็ก ๆ 3,000 ชุด (โดยใช้เส้นยาวหนึ่งหน่วยบนแลตทิซ ซึ่งไม่มีทางตัดกันเอง และสร้างผังซ้อนในผังได้ตามธรรมชาติ) แล้วเทียบสองโปรแกรม ตรงกันหมด

เวอร์ชันเต็ม: เปลี่ยนจากช่องเป็นพื้นที่จริง

ปัญหาที่โผล่มาตอนออกแบบเวอร์ชันนี้

ตอนแรกผมคิดว่าเวอร์ชันเต็มคือแค่เปลี่ยนคำว่าช่องเป็นคำว่าหน้า แล้วจบ จนกระทั่งเจอว่าผังไม่จำเป็นต้องเป็นก้อนเดียว มันแตกเป็นหลายก้อนได้ และก้อนหนึ่ง อาจอยู่ข้างในพื้นที่ปิดของอีกก้อนได้ด้วย ถ้าเหมารวมว่าขอบนอกของทุกก้อนคือทะเล คำตอบของผังซ้อนผังจะผิดทันที เพราะน้ำจากทะเลไปไม่ถึงก้อนข้างในจริง ๆ

ทางแก้คือยิงรังสีลงล่างจากจุดต่ำสุดของขอบนอกแต่ละก้อน แล้วเอาก้อนนั้นไปรวมกับพื้นที่ที่อยู่เหนือกำแพงแนวนอนเส้นที่รังสีชนก่อน ถ้าไม่ชนอะไรเลยก็แปลว่าก้อนนั้นติดทะเลจริง

ตอนตรวจ ผมสุ่มผังบนแลตทิซ 3,000 ชุด โดยใช้เส้นยาวหนึ่งหน่วยซึ่งไม่มีทางตัดกันเอง และสร้างผังซ้อนผังขึ้นมาได้เองตามธรรมชาติ แล้วเทียบเวอร์ชันหน้ากับเวอร์ชันตาราง ตรงกันหมด ตรงนี้สำคัญตรงที่ตัวเทียบเป็นคนละโมเดลกันจริง ๆ ตัวหนึ่งท่วมบนตาราง อีกตัวท่วมบนหน้าของกราฟ

บทเรียนที่ยกไปข้ออื่นได้คือ เวลาสุ่มเคสมาเทียบ ให้ออกแบบตัวสุ่มให้ผลิตโครงสร้างที่เรากลัวที่สุดออกมาได้เอง ไม่งั้นสุ่มเป็นหมื่นชุดก็ไม่เคยเจอผังซ้อนผังสักชุด

พิกัดเป็นล้านจึงแบ่งช่องไม่ได้ ต้องหาพื้นที่ของผังจริง ๆ ซึ่งทำได้เพราะกำแพงไม่ตัดกัน ผังนี้จึงเป็นกราฟระนาบ วิธีมาตรฐานคือแตกกำแพงแต่ละเส้นเป็นครึ่งเส้นสองอัน แล้วเดินไปตามครึ่งเส้นโดยให้พื้นที่อยู่ทางซ้ายมือเสมอ พอเดินวนกลับที่เดิมก็ได้ขอบของพื้นที่หนึ่งผืน

เพราะกำแพงขนานแกน แต่ละจุดมีเพื่อนบ้านได้แค่สี่ทิศ การหาว่า "ครึ่งเส้นถัดไปคืออันไหน" จึงเป็นแค่การกวาดทิศทวนเข็มจากทิศที่ย้อนกลับ

ระวัง

ผังอาจแตกเป็นหลายก้อนที่ไม่ต่อกัน และก้อนหนึ่งอาจอยู่ข้างในพื้นที่ปิดของอีกก้อน ถ้าเหมารวมว่าขอบนอกของทุกก้อนคือทะเล คำตอบจะผิดสำหรับผังซ้อนผัง

วิธีแก้ที่ผมใช้คือ ยิงรังสีลงล่างจากจุดต่ำสุดของขอบนอกแต่ละก้อน แล้วดูว่าไปโดนกำแพงแนวนอนเส้นไหนก่อน พื้นที่ที่อยู่เหนือกำแพงเส้นนั้นคือพื้นที่ที่ห่อก้อนนี้ไว้ แล้วรวมสองอันเข้าด้วยกัน ถ้ายิงแล้วไม่โดนอะไรเลย ก็แปลว่าก้อนนี้อยู่ติดทะเลจริง

ดูโค้ดเต็ม

flood.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,w;
vector<int> X,Y;
vector<array<int,4>> nb;      // เพื่อนบ้านทิศ 0=ตะวันออก 1=เหนือ 2=ตะวันตก 3=ใต้
vector<array<int,4>> nbHe;    // half-edge ที่ออกจากปมนี้ไปทางทิศนั้น
vector<int> heTo,heDir,heFace,heWall;
vector<int> dsu;
int find(int x){ while(dsu[x]!=x) x=dsu[x]=dsu[dsu[x]]; return x; }
void uni(int a,int b){ a=find(a); b=find(b); if(a!=b) dsu[a]=b; }
// เซกเมนต์ทรี range-assign / point-query เก็บ "กำแพงแนวนอนล่าสุด" ที่คลุมพิกัด x นั้น
int SZ; vector<int> tg;
void assign(int node,int l,int r,int ql,int qr,int v){
    if(qr<l||r<ql) return;
    if(ql<=l&&r<=qr){ tg[node]=v; return; }
    int m=(l+r)/2; assign(2*node,l,m,ql,qr,v); assign(2*node+1,m+1,r,ql,qr,v);
}
int query(int node,int l,int r,int p,int cur,const vector<int>&ys){
    if(tg[node]>=0 && (cur<0 || ys[tg[node]]>ys[cur])) cur=tg[node];
    if(l==r) return cur;
    int m=(l+r)/2;
    return p<=m ? query(2*node,l,m,p,cur,ys) : query(2*node+1,m+1,r,p,cur,ys);
}
int main(){
    if(scanf("%d",&n)!=1) return 0;
    X.assign(n+1,0); Y.assign(n+1,0);
    int maxX=0;
    for(int i=1;i<=n;i++){ scanf("%d %d",&X[i],&Y[i]); maxX=max(maxX,X[i]); }
    scanf("%d",&w);
    vector<int> A(w+1),B(w+1);
    nb.assign(n+1,{-1,-1,-1,-1}); nbHe.assign(n+1,{-1,-1,-1,-1});
    heTo.assign(2*w,0); heDir.assign(2*w,0); heWall.assign(2*w,0);
    for(int e=0;e<w;e++){
        int a,b; scanf("%d %d",&a,&b); A[e]=a; B[e]=b;
        int d;                                            // ทิศจาก a ไป b
        if(Y[a]==Y[b]) d = X[b]>X[a] ? 0 : 2;
        else           d = Y[b]>Y[a] ? 1 : 3;
        int h1=2*e,h2=2*e+1;
        heTo[h1]=b; heDir[h1]=d;   heWall[h1]=e; nb[a][d]=b;       nbHe[a][d]=h1;
        heTo[h2]=a; heDir[h2]=d^2; heWall[h2]=e; nb[b][d^2]=a;     nbHe[b][d^2]=h2;
    }
    // เดินหน้า (face) โดยให้พื้นที่อยู่ทางซ้ายมือเสมอ
    heFace.assign(2*w,-1);
    vector<ll> area; vector<int> lowV;
    for(int s=0;s<2*w;s++){
        if(heFace[s]>=0) continue;
        int fid=(int)area.size(); ll ar=0; int low=-1;
        int h=s;
        do{
            heFace[h]=fid;
            int u = heTo[h^1], v = heTo[h];
            ar += (ll)X[u]*Y[v] - (ll)X[v]*Y[u];
            if(low<0 || Y[v]<Y[low] || (Y[v]==Y[low] && X[v]<X[low])) low=v;
            int rev = heDir[h]^2, nd=-1;
            for(int k=3;k>=0;k--){ int dd=(rev+k)%4; if(nbHe[v][dd]>=0){ nd=nbHe[v][dd]; break; } }
            h=nd;
        } while(h!=s);
        area.push_back(ar); lowV.push_back(low);
    }
    int F=(int)area.size();
    int U=F;                                             // ปมเสมือนแทนพื้นที่นอกสุด
    dsu.resize(F+1); for(int i=0;i<=F;i++) dsu[i]=i;
    // กำแพงแนวนอนทุกเส้น เอาไว้ยิงรังสีลงล่างเพื่อหาว่าองค์ประกอบนี้ถูกห่ออยู่ในหน้าไหน
    vector<int> hz; vector<int> ys(w,0);
    for(int e=0;e<w;e++){ ys[e]=Y[A[e]]; if(Y[A[e]]==Y[B[e]]) hz.push_back(e); }
    sort(hz.begin(),hz.end(),[&](int a,int b){ return ys[a]<ys[b]; });
    vector<pair<int,int>> qs;                            // (y ของปมต่ำสุด, face id)
    for(int f=0;f<F;f++) if(area[f]<=0) qs.push_back({Y[lowV[f]],f});
    sort(qs.begin(),qs.end());
    SZ=maxX+2; tg.assign(4*SZ+4,-1);
    size_t pi=0;
    for(auto&[qy,f]:qs){
        while(pi<hz.size() && ys[hz[pi]]<qy){ int e=hz[pi++]; int x1=min(X[A[e]],X[B[e]]),x2=max(X[A[e]],X[B[e]]); assign(1,0,SZ-1,x1,x2-1,e); }
        int px=X[lowV[f]];
        int hit=query(1,0,SZ-1,px,-1,ys);
        if(hit<0) uni(f,U);
        else { int he = (X[heTo[2*hit]]>X[heTo[2*hit+1]]) ? 2*hit : 2*hit+1;  // ครึ่งเส้นที่ชี้ไปทางตะวันออก หน้าอยู่ทางซ้าย คือด้านบน
               uni(f,heFace[he]); }
    }
    vector<int> dist(F+1,INT_MAX);
    deque<int> dq; int src=find(U); dist[src]=0; dq.push_back(src);
    vector<vector<int>> adj(F+1);
    for(int e=0;e<w;e++){ int a=find(heFace[2*e]),b=find(heFace[2*e+1]); if(a!=b){ adj[a].push_back(b); adj[b].push_back(a); } }
    while(!dq.empty()){
        int u=dq.front(); dq.pop_front();
        for(int v:adj[u]) if(dist[u]+1<dist[v]){ dist[v]=dist[u]+1; dq.push_back(v); }
    }
    vector<int> ans;
    for(int e=0;e<w;e++){ int a=find(heFace[2*e]),b=find(heFace[2*e+1]); if(dist[a]==dist[b]) ans.push_back(e+1); }
    printf("%d\n",(int)ans.size());
    for(int e:ans) printf("%d\n",e);
}

เวลาที่วัดได้บนเครื่องผม ผังตารางแลตทิซที่มีจุดราวห้าหมื่นจุดและกำแพงเกือบแสนเส้น ใช้เวลา 170 มิลลิวินาที จากลิมิตสองวินาที

ถ้ายังไม่คุ้นกับการมองปัญหาให้กลายเป็นกราฟที่โจทย์ไม่ได้ให้มา ลองอ่าน กราฟที่โจทย์ไม่ได้ให้มา ซึ่งมีหัวข้อ BFS แบบสองแถวที่ข้อนี้ใช้ด้วย

ท่าที่ติดมือกลับไป

ข้อนี้ยืนอยู่บนสองท่า ท่าแรกคือเรามองกำแพงกับพื้นที่เป็นรูปทรงบนระนาบ แล้วถามคำถามเรื่องรูปทรงเหล่านั้น ซึ่งเรียกรวม ๆ ว่าเรขาคณิตเชิงคำนวณ (computational geometry) ท่าที่สองคือการไล่ระบายพื้นที่ที่ติดกัน ให้เป็นก้อนเดียว ซึ่งทำด้วยการไล่ลึก (DFS) หรือการไล่กว้าง (BFS) ก็ได้ผลเหมือนกัน เพราะเราสนใจแค่ว่าช่องไหนติดกัน ไม่ได้สนใจระยะทาง

ทบทวนพื้นฐาน · เรขาคณิตเชิงคำนวณ

ที่โจทย์เรขาคณิตน่ากลัวกว่าที่ควร เพราะคนมักรีบกระโดดไปคิดเป็นพิกัดทศนิยม แล้วไปเจอปัญหาความคลาดเคลื่อน ท่าที่ปลอดภัยกว่าคือถามก่อนว่าคำตอบขึ้นกับพิกัดจริง หรือขึ้นกับความสัมพันธ์เท่านั้น ข้อนี้เป็นแบบหลัง เราไม่ต้องรู้ว่าน้ำสูงเท่าไรเป็นเลขทศนิยม รู้แค่ว่ากำแพงเส้นไหนเปียกก่อนเส้นไหนก็พอ พอถามแบบนั้นได้ ปัญหาเรขาคณิตก็ยุบเป็นปัญหากราฟที่คิดด้วยจำนวนเต็มได้หมด

อีกท่าที่ใช้ซ้ำได้คือเปลี่ยนพื้นที่ต่อเนื่องให้เป็นช่องกริด ก่อนจะกลับไปทำเวอร์ชันเต็ม ซึ่งเป็นสิ่งที่หัวข้อ "อีกมุมหนึ่ง" ข้างบนทำ กริดตอบผิดในรายละเอียด แต่มันถูกในเรื่องโครงสร้าง จึงใช้เป็นตัวตรวจคำตอบของเวอร์ชันเต็มได้

ส่วนการไล่ลึกกับการไล่กว้าง มีบทปูพื้นเรื่อง BFS บนกราฟสถานะ และคำอธิบายเรื่องการไล่ลึกอยู่ในคลังนี้แล้ว

บิลค่าใช้จ่าย · เทียบสองทางด้วยหน่วยเดียวกัน
ทาง	ขอบเขตที่มันไหว	งานคร่าว ๆ
มองเป็นตารางช่องละหนึ่งหน่วย	พิกัดไม่เกิน 500	250,000 ช่อง
เดินบนพื้นที่จริง	พิกัดถึงหนึ่งล้าน	100,000 เส้น

หน่วยของสองแถวนี้ไม่ใช่หน่วยเดียวกันโดยธรรมชาติ แถวบนนับช่องของตาราง แถวล่างนับกำแพง ซึ่งเป็นประเด็นทั้งหมดของการเปลี่ยนทาง ตารางโตตามพิกัดยกกำลังสอง ที่พิกัดหนึ่งล้านมันจะเป็นหนึ่งล้านล้านช่อง ซึ่งจองหน่วยความจำไม่ได้ตั้งแต่แรก ส่วนจำนวนกำแพงไม่โตตามพิกัดเลย นั่นคือเหตุผลที่ต้องเลิกคิดเป็นช่อง

สรุปบรรทัดเดียว

เวลาที่บอกว่าอะไรพังทีละชั้น มักแปลเป็นระยะทางบนกราฟได้ ที่นี่พื้นที่คือปม กำแพงคือเส้นราคาหนึ่ง และคำถามว่ากำแพงไหนรอด ก็เหลือแค่การเทียบเลขสองตัวที่ BFS คำนวณให้แล้ว

แหล่งที่มา

โจทย์ Flood บน programming.in.th ข้อ 2014 programming.in.th/tasks/2014 (สืบค้น 6 กันยายน 2026)
ต้นทางของโจทย์คือ 19th International Olympiad in Informatics ที่เมืองซาเกร็บ ประเทศโครเอเชีย วันแข่งที่ 1