การโจมตีราชินีของ Hackerrank II

Question

https://www.hackerrank.com/challenges/queens-attack-2/problem

ราชินีกำลังยืนอยู่บนกระดานหมากรุก nxn แถวของกระดานหมากรุกมีหมายเลข 1 ถึง n จากล่างขึ้นบน คอลัมน์ของมันมีหมายเลขตั้งแต่ 1 ถึง n จากซ้ายไปขวา แต่ละตารางบนกระดานแสดงด้วยทูเปิล (r, c) ซึ่งอธิบายถึงแถว r และคอลัมน์ c ที่ซึ่งสี่เหลี่ยมนั้นตั้งอยู่

ราชินีกำลังยืนอยู่ที่ตำแหน่ง (rq, cq) และในการเคลื่อนไหวเพียงครั้งเดียวเธอสามารถโจมตีจัตุรัสใดก็ได้ในแปดทิศทาง (ซ้ายขวาขึ้นลงหรือสี่แนวทแยงมุม) ในแผนภาพด้านล่างวงกลมสีเขียวแสดงถึงเซลล์ทั้งหมดที่ราชินีสามารถโจมตีได้จาก (4,4):

มี\$k\$อุปสรรคบนกระดานหมากรุกป้องกันราชินีจากการโจมตีจัตุรัสใด ๆ ที่มีสิ่งกีดขวางขวางเส้นทางของราชินีไปที่มัน ตัวอย่างเช่นสิ่งกีดขวางที่ตำแหน่ง\$(3,5)\$ในแผนภาพด้านบนจะป้องกันไม่ให้ราชินีโจมตีเซลล์\$(3,5)\$, \$(2,6)\$และ\$(1,7)\$:

ระบุตำแหน่งราชินีและตำแหน่งของอุปสรรคทั้งหมดค้นหาและพิมพ์จำนวนช่องสี่เหลี่ยมที่ราชินีสามารถโจมตีจากตำแหน่งของเธอได้ที่\$(r_q,c_q)\$.

รูปแบบการป้อนข้อมูล

บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวที่คั่นด้วยช่องว่างซึ่งอธิบายค่าตามลำดับของ\$n\$(ความยาวด้านข้างของกระดาน) และ\$k\$ (จำนวนอุปสรรค)

บรรทัดถัดไปประกอบด้วยจำนวนเต็มสองตัวที่คั่นด้วยช่องว่างซึ่งอธิบายค่าตามลำดับของ\$r_q\$และ\$c_q\$แสดงถึงตำแหน่งของราชินี

แต่ละบรรทัด\$i\$ของ\$k\$บรรทัดต่อมาประกอบด้วยจำนวนเต็มที่คั่นด้วยช่องว่างสองตัวซึ่งอธิบายค่าตามลำดับ\$r_i\$ของ\$c_i\$และแสดงตำแหน่งของอุปสรรค\$i\$.

ข้อ จำกัด

\$ 0 \leq n \leq 100000\$

\$ 0 \leq k \leq 100000\$

เซลล์เดียวอาจมีอุปสรรคมากกว่าหนึ่งอย่าง อย่างไรก็ตามรับประกันได้ว่าจะไม่มีสิ่งกีดขวางที่ตำแหน่ง\$(r_q,c_q)\$ ที่ตั้งของราชินี

รูปแบบเอาต์พุต

พิมพ์จำนวนช่องสี่เหลี่ยมที่ราชินีสามารถโจมตีได้จากตำแหน่ง

อินพุตตัวอย่าง 0

\$4\$ \$0\$

\$4\$ \$4\$

ตัวอย่างผลลัพธ์ 0

\$9\$

คำอธิบาย 0

สมเด็จพระราชินีจะยืนอยู่ในตำแหน่งที่\$(4,4)\$ในวันที่\$4\$x \$4\$ กระดานหมากรุกโดยไม่มีอุปสรรค:

จากนั้นเราจะพิมพ์จำนวนสี่เหลี่ยมที่เธอสามารถโจมตีได้จากตำแหน่งนั้นซึ่งก็คือ\$9\$.

แนวทางของฉัน:

แทนที่จะวนซ้ำทุกจุดในเส้นทางควีนส์เนื่องจากจะต้องใช้ทรัพยากรอย่างเข้มข้นเมื่อ n สูงมากฉันแยกเส้นทางออกเป็น 8 ทิศทางที่แตกต่างกัน (ขึ้นซ้ายขึ้นขึ้นขวาขวา ฯลฯ )

int u, d, l, r, ul, ur, dl, dr;
u = d = l = r = ul = ur = dl = dr = 0;
bool modified[8] = { false };

กว่าที่ฉันจะตรวจสอบว่ามีสิ่งกีดขวางในเส้นทางหรือไม่โดยการตรวจสอบว่าราชินี x = สิ่งกีดขวาง x หรือราชินี y = อุปสรรค y และถ้ามันอยู่บนเส้นทางแนวตั้ง / แนวนอนของราชินีฉันจะหาระยะทางโดยการคำนวณเดลต้า - 1 และ เพื่อหาจุดทแยงมุมที่ฉันรู้เนื่องจากจุดนั้นต้องมีความชัน 1 หรือ -1 เพื่อให้อยู่ในเส้นทางราชินีดังนั้นฉันจึงตรวจสอบว่า | y ของราชินี - y ของอุปสรรค | = | x ของราชินี - x อุปสรรค | และถ้ามันเป็นจริงมากกว่าที่ฉันจะหาเดลต้าระหว่าง x หรือ y เป็นอย่างใดอย่างหนึ่งและถ้าไม่มีสิ่งกีดขวางฉันจะใช้ edge เพื่อหาระยะ ฉันตรวจสอบเฉพาะเพื่อดูว่าสิ่งกีดขวางอยู่ในเส้นทางหรือไม่จากนั้นคำนวณจุดที่เป็นไปได้มากกว่าที่จะทำเครื่องหมายทิศทางว่าแก้ไขแล้วดังนั้นหากไม่ได้ทำเครื่องหมายมากกว่าหมายความว่าไม่มีสิ่งกีดขวางในเส้นทางดังนั้นฉันจึงหาระยะห่างจากขอบโดยใช้:

if (!modified[0]) u = n - qy;
if (!modified[1]) d = qy - 1;
if (!modified[2]) l = qx - 1;
if (!modified[3]) r = n - qx;
if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

ขออภัยสำหรับรูปแบบที่ไม่เป็นระเบียบนี่เป็นครั้งแรกของฉันใน stackoverflow / stackexchange

รหัสเต็ม:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int queensAttack(const int &n, const int &k, const int & qy, const int & qx, const vector<vector<int>> &obstacles) {
    int u, d, l, r, ul, ur, dl, dr;                 //up, down, left, right, up-left, up-right, down-left, down-right
    u = d = l = r = ul = ur = dl = dr = 0;          
    bool modified[8] = { false };                   //if modified is still false after looping through obstacles check that means no obstacle at path

    for (int i = 0; i < obstacles.size(); i++) {    //loop through all obstacles, if it is in path get distance to queen
        int temp{};
        if (obstacles[i][1] == qx) {                //if obstacle x = queen x than they are on same column
            if (obstacles[i][0] > qy) {             //check if its above or below queen
                temp = obstacles[i][0] - qy - 1;    
                if (modified[0] && u > temp || !modified[0]) {    //only assign distance if it was never assigned before or less than it  
                    u = temp;
                }
                modified[0] = true;
            }
            else {
                temp = qy - obstacles[i][0] - 1;
                if (modified[1] && d > temp || !modified[1]) {
                    d = temp;
                }
                modified[1] = true;
            }
        }
        if (obstacles[i][0] == qy) {
            if (obstacles[i][1] < qx) {
                temp = qx - obstacles[i][1] - 1;
                if (modified[2] && l > temp || !modified[2]) {
                    l = temp;
                }
                modified[2] = true;
            }
            else {
                temp = obstacles[i][1] - qx - 1;
                if (modified[3] && r > temp || !modified[3]) {
                    r = temp;
                }
                modified[3] = true;
            }
        }
        if (abs(qy - obstacles[i][0]) == abs(qx - obstacles[i][1])) {   //diagonals, checking if it is on the diagonal path of the queen
            if (obstacles[i][0] > qy && obstacles[i][1] < qx) {         //check if it is top left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[4] && ul > temp || !modified[4]) {
                    ul = temp;
                }
                modified[4] = true;
            }
            if (obstacles[i][0] > qy && obstacles[i][1] > qx) {         //check if it is top right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[5] && ur > temp || !modified[5]) {
                    ur = temp;
                }
                modified[5] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] < qx) {         //check if it is bottom left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[6] && dl > temp || !modified[6]) {
                    dl = temp;
                }
                modified[6] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] > qx) {         //check if it is bottom right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[7] && dr > temp || !modified[7]) {
                    dr = temp;
                }
                modified[7] = true;
            }
        }
    }
    if (!modified[0]) u = n - qy;                               //if they never been modified means no obstacles in path so use calculate distance from edge to queen (probably better way to do this)
    if (!modified[1]) d = qy - 1;
    if (!modified[2]) l = qx - 1;
    if (!modified[3]) r = n - qx;
    if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
    if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
    if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
    if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

    return u + d + l + r + ul + ur + dl + dr;
}

int main() {

    int n, k, qx, qy;
    cin >> n >> k >> qy >> qx;
    const int c = k;
    vector<vector<int>> ob(k);
    for (int i = 0; i < k; i++) {
        ob[i].resize(2);
        cin >> ob[i][0] >> ob[i][1];
    }

    cout << queensAttack(n,k,qy,qx,ob);

    return 0;
}

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

ฉันสามารถรับคำติชมหรือคำแนะนำเพื่อการปรับปรุงได้หรือไม่? ขอบคุณ!

Answer 1

ข้อสังเกตทั่วไป

เป็นการดีที่คุณจะใส่ส่วนหัวที่จำเป็นแทนที่จะใช้ส่วนหัว catchall ที่ Hacker Rank ให้มา คุณไม่รวมส่วนหัวที่ไม่จำเป็นรหัสรวบรวมโดยไม่ต้องหรือcmath algorithmรวมเฉพาะสิ่งที่จำเป็นในการคอมไพล์โค้ด การใช้ส่วนหัวที่ไม่จำเป็นสามารถเพิ่มเวลาในการสร้างได้เนื่องจาก C ++ สร้างไฟล์ชั่วคราวและคัดลอกส่วนหัวลงในไฟล์ชั่วคราวนั้น

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

รหัสนี้จะรักษายากมาก บางเรื่องอ่านง่ายมากและบางส่วนแทบอ่านไม่ออก ตัวอย่างบางส่วนของโค้ดที่แทบไม่สามารถอ่านได้ ได้แก่ :

    int u, d, l, r, ul, ur, dl, dr;                 //up, down, left, right, up-left, up-right, down-left, down-right
    u = d = l = r = ul = ur = dl = dr = 0;

และ

    if (!modified[0]) u = n - qy;        //if they never been modified means no obstacles in path so use calculate distance from edge to queen (probably better way to do this)
    if (!modified[1]) d = qy - 1;
    if (!modified[2]) l = qx - 1;
    if (!modified[3]) r = n - qx;
    if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
    if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
    if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
    if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

ฟังก์ชันqueensAttack()คือ 88 บรรทัดและฟังก์ชันเดียวที่มีขนาดยากมากที่จะเขียนอ่านแก้ไขข้อบกพร่องหรือดูแลรักษา

หลีกเลี่ยง using namespace std;

หากคุณเขียนโค้ดอย่างมืออาชีพคุณอาจจะต้องเลิกใช้using namespace std;คำสั่งดังกล่าว โค้ดจะกำหนดได้ชัดเจนยิ่งขึ้นว่าcoutมาจากไหนและตัวระบุอื่น ๆ มาจาก ( std::cin, std::cout) เมื่อคุณเริ่มใช้เนมสเปซในโค้ดของคุณจะเป็นการดีกว่าที่จะระบุว่าแต่ละฟังก์ชันมาจากที่ใดเนื่องจากอาจมีการชนกันของชื่อฟังก์ชันจากเนมสเปซที่ต่างกัน ตัวระบุที่coutคุณสามารถแทนที่ภายในคลาสของคุณเองและคุณอาจแทนที่ตัวดำเนินการ<<ในชั้นเรียนของคุณเองได้เช่นกัน นี้คำถามที่แตกล้นกล่าวถึงนี้ในรายละเอียดมากขึ้น

ความซับซ้อน

ฟังก์ชันqueensAttack()ซับซ้อนเกินไป (ทำมากเกินไป) ควรแยกออกเป็นฟังก์ชันฉันเห็นฟังก์ชันที่เป็นไปได้อย่างน้อย 3 ฟังก์ชันและอาจมากกว่านั้น เทคนิคการออกแบบที่ดีคือการแบ่งปัญหาออกเป็นปัญหาเล็ก ๆ แยกจากกันจนกว่าแต่ละปัญหาจะแก้ได้ง่ายมาก นอกจากนี้ยังทำให้โค้ดสามารถบำรุงรักษาได้มากขึ้น

นอกจากนี้ยังมีหลักการเขียนโปรแกรมที่เรียกว่าหลักการความรับผิดชอบเดียวที่ใช้ที่นี่ เดี่ยวรับผิดชอบหลักการฯ :

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

เลขวิเศษ

มี Magic Numbers ในqueensAttack()ฟังก์ชัน (0 ถึง 7) อาจเป็นการดีกว่าที่จะสร้างค่าคงที่เป็นสัญลักษณ์เพื่อให้โค้ดอ่านง่ายขึ้นและดูแลรักษาง่ายขึ้นในกรณีนี้สามารถใช้ enum ได้ ตัวเลขเหล่านี้อาจถูกใช้ในหลายสถานที่และสามารถเปลี่ยนได้โดยการแก้ไขเพียงบรรทัดเดียวทำให้การบำรุงรักษาง่ายขึ้น

ค่าคงที่ตัวเลขในรหัสบางครั้งเรียกว่าMagic Numbersเนื่องจากไม่มีความหมายที่ชัดเจนสำหรับพวกเขา มีการอภิปรายเรื่องนี้อยู่ในStackOverflow

ต้องการunsignedประเภทเป็นจำนวนเต็มสำหรับตัวแปรดัชนี

เมื่อสร้างดัชนีลงในอาร์เรย์หรือคอนเทนเนอร์ประเภทอื่น ๆ ควรใช้ประเภทที่ไม่ได้ลงนามเช่นsize_tแทนที่จะเป็นจำนวนเต็ม ประเภทที่ไม่ได้ลงชื่อไม่สามารถกลายเป็นค่าลบและการใช้ดัชนีเชิงลบอาจทำให้เกิดพฤติกรรมที่ไม่ได้กำหนด size()ฟังก์ชั่นทุกประเภทภาชนะผลตอบแทนsize_tและรหัสที่มีการสร้างคำเตือนไม่ตรงกันพิมพ์สำหรับวง:

    for (int i = 0; i < obstacles.size(); i++) {    //loop through all obstacles, if it is in path get distance to queen

การประกาศตัวแปร

ประกาศและเริ่มต้นตัวแปรหนึ่งตัวต่อบรรทัด แม้ว่าผลลัพธ์ต่อไปนี้จะทำให้มีพื้นที่แนวตั้งเพิ่มขึ้นมากมาย แต่ก็อ่านและดูแลรักษาได้ง่ายขึ้น:

    int u = 0;
    int d = 0;
    int l = 0;
    int r = 0;
    int ul = 0;
    int ur = 0;
    int dl = 0;
    int dr = 0;
    bool modified[8] = { false };

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

ชื่อตัวแปร

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

รหัสแห้ง

มีหลักการเขียนโปรแกรมที่เรียกว่าDon't Repeat Yourself Principleบางครั้งเรียกว่า DRY code หากคุณพบว่าตัวเองใช้รหัสเดิมซ้ำหลายครั้งควรห่อหุ้มไว้ในฟังก์ชันจะดีกว่า หากเป็นไปได้ที่จะวนซ้ำโค้ดที่สามารถลดการทำซ้ำได้เช่นกัน

นี่เป็นรหัสที่ซ้ำซากมาก:

        if (abs(qy - obstacles[i][0]) == abs(qx - obstacles[i][1])) {   //diagonals, checking if it is on the diagonal path of the queen
            if (obstacles[i][0] > qy && obstacles[i][1] < qx) {         //check if it is top left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[4] && ul > temp || !modified[4]) {
                    ul = temp;
                }
                modified[4] = true;
            }
            if (obstacles[i][0] > qy && obstacles[i][1] > qx) {         //check if it is top right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[5] && ur > temp || !modified[5]) {
                    ur = temp;
                }
                modified[5] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] < qx) {         //check if it is bottom left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[6] && dl > temp || !modified[6]) {
                    dl = temp;
                }
                modified[6] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] > qx) {         //check if it is bottom right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[7] && dr > temp || !modified[7]) {
                    dr = temp;
                }
                modified[7] = true;
            }

Answer 2

รหัสของคุณ:

1. ดีสำหรับคุณที่จะรวมเฉพาะส่วนหัวที่คุณคิดว่าคุณต้องการ คุณไม่ได้ใช้อะไรจาก<cmath>หรือ<algorithm>แม้ว่า

2. using namespace std;เป็นความชั่วร้ายธรรมดา เนมสเปซนั้นไม่ได้ออกแบบมาสำหรับการรวมจึงไม่มีรายการเนื้อหาที่ครอบคลุมคงที่และเชื่อถือได้
   โปรดดู " เหตุใด " จึงใช้ namespace std; " ถือเป็นการปฏิบัติที่ไม่ดี? "สำหรับรายละเอียด

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

4. ดูstd::spanการส่งผ่านมุมมองของวัตถุที่อยู่ติดกัน
   โปรดดูที่ " " สแปน "คืออะไรและควรใช้เมื่อใด "

5. C ++ มีลูปสำหรับช่วงตั้งแต่ C ++ 11 เกิดข้อผิดพลาดน้อยกว่าการเล่นซอกับดัชนีหรือตัวทำซ้ำด้วยตนเอง

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

7. std::vectorของความยาวสองเป็นมากยากจนข้อมูลโครงสร้างการจัดเก็บพิกัดของจุด ไม่มีประสิทธิภาพมากไม่สะดวกและเกิดข้อผิดพลาดได้ง่าย อย่างน้อยการใช้งานstd::pair, std::arrayหรือstd::tupleถ้าคุณปฏิเสธที่จะลงทุนบรรทัดเดียวสำหรับชนิดที่กำหนดเองจิ๊บจ๊อย

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

9. return 0;เป็นนัยสำหรับmain()ใน C ++ และ C99 +

แนวทางของคุณสามารถปรับให้เหมาะสมและง่ายขึ้นเพิ่มเติม:

1. ใช้ระบบพิกัดควีนเป็นศูนย์กลาง การตรวจสอบทั้งหมดเป็นเรื่องเกี่ยวกับราชินีและตอนนี้ง่ายกว่ามาก

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

#include <algorithm>
#include <iostream>

int main() {
    int x, y, k, qx, qy;
    std::cin >> x >> k >> qx >> qy;

    int d = qy,
        l = qx,
        u = x + 1 - qy,
        r = x + 1 - qx;
    int dl = std::min(d, l),
        dr = std::min(d, r),
        ul = std::min(u, l),
        ur = std::min(u, r);
    auto update = [](int a, int& b, int& c){
        if (a < 0)
            b = std::min(b, -a);
        else
            c = std::min(c, a);
    };

    while (k--) {
        std::cin >> x >> y;
        x -= qx;
        y -= qy;
        if (!x)
            update(y, d, u);
        else if (!y)
            update(x, l, r);
        else if (x == y)
            update(x, dl, ur);
        else if (x == -y)
            update(x, ul, dr);
    }

    std::cout << (d + u + l + r + dl + dr + ul + ur - 8);
}

ระวัง: รหัสข้างต้นได้รับการพิสูจน์แล้วว่าถูกต้องเท่านั้นห้ามเรียกใช้