7.4 ช่องข้างเคียง

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

ช่องข้างเคียง 4 ทิศและ 8 ทิศ

ช่องแถว r คอลัมน์ c มีช่องติดกันด้านข้าง 4 ช่อง คือบน ล่าง ซ้าย ขวา ถ้านับช่องทแยงด้วยจะเป็น 8 ช่อง โจทย์จะบอกเสมอว่าติดกันแบบไหน ต้องอ่านให้ดี

ขึ้นไปหนึ่งช่องคือแถวลดลงหนึ่ง r - 1 ลงไปหนึ่งช่องคือ r + 1 ไปทางซ้ายคือคอลัมน์ลดลง c - 1 ไปทางขวาคือ c + 1 ทแยงคือเปลี่ยนทั้งสองค่าพร้อมกัน

อาเรย์ทิศทาง dr กับ dc

จะดูช่องข้างเคียงทั้งสี่ เขียน if สี่ก้อนก็ได้ แต่สี่ก้อนนั้นเหมือนกันเกือบทุกตัวอักษร ต่างกันแค่ตัวเลขที่บวกกับ r และ c ถ้าแก้ก้อนหนึ่งแล้วลืมแก้อีกก้อน ก็ได้บั๊กทันที วิธีที่ใช้กันทั่วไปคือเก็บตัวเลขที่ต้องบวกไว้ในอาเรย์สองตัว

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

อ่านคู่กันในแนวตั้ง ทิศที่ 0 คือ (-1, 0) ขึ้นบน ทิศที่ 1 คือ (1, 0) ลงล่าง ทิศที่ 2 คือ (0, -1) ไปซ้าย ทิศที่ 3 คือ (0, 1) ไปขวา แล้วใช้ลูปเดียวเดินครบทุกทิศ ช่องข้างเคียงทิศที่ d คือ (r + dr[d], c + dc[d])

ตัวอย่างนี้นับว่าแต่ละช่องมี # ติดกันใน 4 ทิศกี่ช่อง แล้วพิมพ์เป็นตารางตัวเลข

#include <stdio.h>

char map[100][101];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    for (int r = 0; r < rows; r++) {
        scanf("%s", map[r]);
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int count = 0;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d]; // (1)!
                int nc = c + dc[d];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && map[nr][nc] == '#') { // (2)!
                    count++;
                }
            }
            printf("%d", count);
        }
        printf("\n");
    }
    return 0;
}

1. nr กับ nc ย่อมาจาก next row กับ next column คือพิกัดของช่องข้างเคียงทิศที่ d
2. เช็กก่อนว่าพิกัดอยู่ในตาราง แล้วค่อยดูว่าเป็น # ไหม ลำดับนี้สำคัญ ดูหัวข้อถัดไป

3 4
#..#
..#.
#...

0120
2102
0110

ช่อง (1, 0) ได้ 2 เพราะช่องบน (0, 0) กับช่องล่าง (2, 0) เป็น # ส่วนช่องซ้ายไม่มี เพราะอยู่ขอบตาราง

เช็กขอบตารางทุกครั้ง

ช่องที่อยู่ขอบมีข้างเคียงไม่ครบ ช่องมุมบนซ้าย (0, 0) ถ้าขึ้นบนจะได้แถว -1 ซึ่งไม่มีอยู่จริง จึงต้องเช็กสี่ข้อให้ผ่านทั้งหมดก่อนแตะช่องนั้น

nr >= 0 && nr < rows && nc >= 0 && nc < cols

เงื่อนไขที่ต่อด้วย && หยุดทันทีที่เจอข้อที่เป็นเท็จ ตามเรื่อง short-circuit ในบทที่ 3 ถ้า nr เป็น -1 ข้อแรกเป็นเท็จ ส่วน map[nr][nc] == '#' ที่อยู่ท้ายสุดจะไม่ถูกทำเลย จึงไม่มีการอ่านช่องที่ไม่มีจริง ถ้าสลับเอา map[nr][nc] == '#' ไว้ข้างหน้า จะอ่านก่อนเช็ก ซึ่งผิด

8 ทิศ

เพิ่มอีกสี่ทิศทแยงเข้าไปในอาเรย์ เรียงทีละแถวของภาพ 3 × 3 ตั้งแต่บนซ้ายถึงล่างขวา โดยข้ามช่องตรงกลาง จะตรวจด้วยตาได้ง่ายว่าครบ

int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

ตัวอย่างนี้เป็นแผนที่ความสูงของภูเขา หา ยอดเขา คือช่องที่สูงกว่าทุกช่องข้างเคียงทั้ง 8 ทิศ ช่องข้างเคียงที่อยู่นอกแผนที่ไม่ต้องเทียบ

#include <stdio.h>

int height[100][100];
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main()
{
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            scanf("%d", &height[r][c]);
        }
    }
    int peaks = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int is_peak = 1;
            for (int d = 0; d < 8; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    if (height[nr][nc] >= height[r][c]) {
                        is_peak = 0;
                    }
                }
            }
            if (is_peak) {
                printf("peak at row %d column %d\n", r + 1, c + 1);
                peaks++;
            }
        }
    }
    printf("%d peaks\n", peaks);
    return 0;
}

4 5
1 2 1 0 3
2 6 2 1 2
1 2 3 2 7
0 1 2 5 4

peak at row 1 column 5
peak at row 2 column 2
peak at row 3 column 5
3 peaks

ช่องสูง 5 ที่แถว 4 คอลัมน์ 4 ไม่ใช่ยอดเขา เพราะช่องทแยงขวาบนสูง 7 ถ้าโจทย์นี้ใช้แค่ 4 ทิศ ช่องนี้จะกลายเป็นยอดเขา คำตอบจึงขึ้นกับว่าใช้กี่ทิศ เปลี่ยน dr dc เป็นแบบ 4 ทิศ และเลข 8 ในลูปเป็น 4 แล้วลองรันดู

จำลองทีละรอบ

โจทย์อีกแบบให้ตารางที่เปลี่ยนไปตามเวลา ทุกรอบแต่ละช่องจะเปลี่ยนตามช่องข้างเคียงของมัน ตัวอย่างที่รู้จักกันดีคือ Game of Life ของนักคณิตศาสตร์ John Conway ช่อง # คือเซลล์ที่มีชีวิต . คือช่องว่าง ทุกรอบเปลี่ยนพร้อมกันทั้งตารางตามกฎนี้ โดยนับเซลล์ที่มีชีวิตในช่องข้างเคียง 8 ทิศ

• เซลล์ที่มีชีวิต ถ้ามีเพื่อนบ้าน 2 หรือ 3 เซลล์ จะอยู่ต่อ ถ้าน้อยหรือมากกว่านั้นจะตาย
• ช่องว่าง ถ้ามีเพื่อนบ้านพอดี 3 เซลล์ จะเกิดเซลล์ใหม่

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

#include <stdio.h>

char cur[100][101], next_map[100][101];
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main()
{
    int rows, cols, rounds;
    scanf("%d %d %d", &rows, &cols, &rounds);
    for (int r = 0; r < rows; r++) {
        scanf("%s", cur[r]);
    }
    for (int t = 0; t < rounds; t++) {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int alive = 0;
                for (int d = 0; d < 8; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cur[nr][nc] == '#') {
                        alive++;
                    }
                }
                if (cur[r][c] == '#' && (alive == 2 || alive == 3)) {
                    next_map[r][c] = '#'; // (1)!
                } else if (cur[r][c] == '.' && alive == 3) {
                    next_map[r][c] = '#';
                } else {
                    next_map[r][c] = '.';
                }
            }
        }
        for (int r = 0; r < rows; r++) { // (2)!
            for (int c = 0; c < cols; c++) {
                cur[r][c] = next_map[r][c];
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        printf("%s\n", cur[r]);
    }
    return 0;
}

1. เขียนลง next_map เท่านั้น ระหว่างคิดรอบนี้ cur ต้องเป็นสภาพของรอบที่แล้วตลอด
2. คิดครบทุกช่องแล้วถึงคัดลอกกลับมาที่ cur เพื่อเริ่มรอบถัดไป คัดลอกแค่ cols ตัวแรก '\0' ที่ cur[r][cols] จาก scanf จึงยังอยู่ และพิมพ์ด้วย %s ได้

8 8 1
........
.##.....
.##.....
........
........
....###.
........
........

........
.##.....
.##.....
........
.....#..
.....#..
.....#..
........

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

ลองทำให้พัง

แบบที่ 1 ไม่เช็กขอบ

ใช้แผนที่ 3 × 4 เดียวกับโปรแกรม count4 แต่ประกาศขนาดพอดี char map[3][4] ใส่ค่าในโค้ด และตัดการเช็กขอบออก เหลือแค่ if (map[nr][nc] == '#')

#include <stdio.h>

char map[3][4] = {
    "#..#",
    "..#.",
    "#..."
};
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 4; c++) {
            int count = 0;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (map[nr][nc] == '#') {
                    count++;
                }
            }
            printf("%d", count);
        }
        printf("\n");
    }
    return 0;
}

คอมไพล์ผ่านโดยไม่มีคำเตือนทั้งแบบ -Wall และ -O2 โปรแกรมไม่พัง บนเครื่องที่เขียนเอกสารนี้ได้

0120
3103
0110

คำตอบที่ถูกคือ 2102 ในแถวกลาง ช่องซ้ายสุดและขวาสุดของแถวกลางนับเกินมาช่องละหนึ่ง เพราะตารางเรียงต่อกันเป็นแถวยาวในหน่วยความจำตามหน้า 7.1 map[1][-1] จึงคือตัวสุดท้ายของแถว 0 และ map[1][4] คือตัวแรกของแถว 2 ซึ่งบังเอิญเป็น # ทั้งคู่ ส่วนแถวบนสุดและล่างสุดอ่านไปนอกอาเรย์เลย บนเครื่องนี้บังเอิญไม่เจอ # แต่เครื่องอื่นอาจได้ค่าอื่น หรือโปรแกรมพัง

บั๊กนี้น่ากลัวเพราะชุดทดสอบเล็กมักผ่าน ถ้าประกาศอาเรย์ [100][101] แต่ตารางในชุดทดสอบเล็ก ช่องที่ล้นไปจะเป็นช่องว่างที่ไม่มีใครใช้ จะไปตกเอาชุดที่ R และ C เต็มขอบเขตพอดี

แบบที่ 2 เขียนผลทับตารางเดิม

ในโปรแกรม life ถ้าเขียนผลลง cur ตรงๆ เพื่อประหยัดตาราง ตัดส่วนคัดลอกออก แล้วรันกับแท่งแนวนอนสามช่องหนึ่งรอบ

#include <stdio.h>

char cur[100][101];
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main()
{
    int rows, cols, rounds;
    scanf("%d %d %d", &rows, &cols, &rounds);
    for (int r = 0; r < rows; r++) {
        scanf("%s", cur[r]);
    }
    for (int t = 0; t < rounds; t++) {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int alive = 0;
                for (int d = 0; d < 8; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && cur[nr][nc] == '#') {
                        alive++;
                    }
                }
                if (cur[r][c] == '#' && (alive == 2 || alive == 3)) {
                    cur[r][c] = '#';
                } else if (cur[r][c] == '.' && alive == 3) {
                    cur[r][c] = '#';
                } else {
                    cur[r][c] = '.';
                }
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        printf("%s\n", cur[r]);
    }
    return 0;
}

5 5 1
.....
.....
.###.
.....
.....

.....
..##.
.#.#.
.....
.....

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

สรุป

• ช่องข้างเคียง 4 ทิศคือบน ล่าง ซ้าย ขวา 8 ทิศเพิ่มช่องทแยง อ่านโจทย์ให้ดีว่าใช้แบบไหน
• เก็บทิศไว้ใน dr dc แล้วใช้ลูปเดียว ช่องข้างเคียงคือ (r + dr[d], c + dc[d])
• เช็ก nr >= 0 && nr < rows && nc >= 0 && nc < cols ก่อนแตะช่องเสมอ หรือเว้นขอบหนึ่งชั้นแล้วเริ่มที่ 1
• ออกนอกขอบไม่พังให้เห็น แต่ไปหยิบช่องของแถวข้างๆ มาแทน
• จำลองทีละรอบ ให้คิดจากตารางเดิม เขียนผลลงตารางใหม่ แล้วค่อยคัดลอกกลับ