อิฐล้มเมื่อถูกโจมตีใน C++

สมมติว่าเรามีตารางค่าไบนารี (0 และ 1 วินาที) โดยที่ 1 ในเซลล์เป็นตัวแทนของก้อนอิฐ อิฐจะไม่หล่นเมื่อเป็นไปตามเงื่อนไขเหล่านี้ -

• อิฐทั้งสองก้อนเชื่อมต่อโดยตรงกับด้านบนของกริด

• หรืออิฐที่อยู่ติดกัน (บน ล่าง ซ้าย ขวา) อย่างน้อยหนึ่งก้อนจะไม่หล่น

เราจะทำการลบบางส่วนตามลำดับ ในแต่ละกรณี เราต้องการลบที่ตำแหน่ง (i, j) อิฐ (ถ้ามี) ในตำแหน่งนั้นจะหายไป จากนั้นก้อนอิฐอื่นๆ อาจหล่นลงมาเนื่องจากการถูกลบนั้น เราต้องหาอาร์เรย์ที่แสดงถึงจำนวนอิฐที่จะลดลงหลังจากการลบแต่ละครั้งตามลำดับ

ดังนั้น หากอินพุตเป็นเหมือน grid =[[1,0,0,0],[1,1,1,0]] และ hits =[[1,0]] ผลลัพธ์จะเป็น [2], นี่เป็นเพราะถ้าเราเอาก้อนอิฐที่วางอยู่ที่ (1, 0) อิฐที่ (1, 1) และ (1, 2) จะลดลง ดังนั้นเราควรคืน 2.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ dir ขนาด:4 x 2, dir :={{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ i, j, กริด

• ถ้าเมื่อ (i,j) อยู่ภายในขอบเขตกริดและกริด[i, j] ไม่เท่ากับ 1 ดังนั้น−

  • คืนค่า 0

• ยกเลิก :=1

• กริด[i, j] :=2

• สำหรับการเริ่มต้น k :=0 เมื่อ k <4 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

  • ret :=ret + dfs(i + dir[k, 0], j + dir[k, 1], กริด)

• รีเทิร์น

• กำหนดฟังก์ชัน notConnected() ซึ่งจะใช้ x, y และ grid

• สำหรับการเริ่มต้น k :=0 เมื่อ k <4 อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

  • nx :=x + dir[k, 0], ny :=y + dir[k, 1]

  • ถ้า (nx, ny) อยู่ในช่วงของกริด ดังนั้น −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้า grid[nx, ny] เหมือนกับ 2 แล้ว −

    • คืนความจริง

• คืนค่า จริง เมื่อ x เท่ากับ 0

• จากวิธีหลัก ให้ทำดังนี้ −

• กำหนดอาร์เรย์ ret

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ Hit อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • grid[hits[i, 0], hits[i, 1]] :=grid[hits[i, 0], hits[i, 1]] - 1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของกริด อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • dfs(0, i, กริด)

• ย้อนกลับอาร์เรย์ฮิต

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ Hit อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • x :=hits[i, 0], y :=hits[i, 1]

  • ถ้า grid[x, y] เหมือนกับ 1 และ notConnected(x, y, grid) แล้ว −

    • แทรก dfs(x, y, grid) ที่ส่วนท้ายของ ret

  • มิฉะนั้น

    • ใส่ 0 ต่อท้าย ret

• ย้อนกลับอาร์เรย์ ret

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include ใช้เนมสเปซ std;void print_vector(vector v){ cout <<"["; for(int i =0; i>&grid){ if (i <0 || j <0 || i>=grid.size() || j>=grid [0].size() || grid[i][j] !=1) { return 0; } int ret =1; ตาราง[i][j] =2; สำหรับ (int k =0; k <4; k++) { ret +=dfs(i + dir[k][0], j + dir[k][1], grid); } ผลตอบแทนย้อนหลัง; } bool notConnected (int x, int y, vector>&grid){ สำหรับ (int k =0; k <4; k++) { int nx =x + dir[k][0]; int ny =y + dir[k][1]; ถ้า (nx <0 || ny <0 || nx>=grid.size() || ny>=grid[0].size()) ดำเนินการต่อ; if (grid[nx][ny] ==2) { คืนค่าจริง; } } ผลตอบแทน x ==0; } vector hitBricks(vector>&grid, vector>&hits){ vector ret; สำหรับ (int i =0; i > v ={{1,0,0,0},{1,1,1,0}}; เวกเตอร์<เวกเตอร์> v1 ={{1,0}}; print_vector(ob.hitBricks(v, v1));}

อินพุต

ผลลัพธ์

[2, ]