ค้นหาพิกัดของจุดยอดที่สี่ของสี่เหลี่ยมผืนผ้าที่มีจุดยอด 3 จุดในPython

สมมติว่าเรามีตารางขนาด Q * P ตารางนี้ประกอบด้วยเครื่องหมายดอกจัน '*' สามดอก และทุกเซลล์อื่นๆ จะมีจุด '.' โดยที่ '*' ใช้สำหรับจุดยอดของสี่เหลี่ยมผืนผ้า เราต้องหาพิกัดของจุดยอดที่หายไป เราจะพิจารณาการจัดทำดัชนีแบบ 1-based

ดังนั้น หากอินพุตเป็นเหมือน grid =[ ".*.", "...", "*.*" ] ผลลัพธ์จะเป็น [1, 3] นี่คือพิกัดที่ขาดหายไป

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

• p :=จำนวนแถว

• q :=จำนวนคอลัมน์

• row :=ทำแผนที่สำหรับหมายเลขแถวทั้งหมด และค่าที่เกี่ยวข้องคือ 0

• col :=สร้างแผนที่สำหรับหมายเลขคอลัมน์ทั้งหมด และค่าที่เกี่ยวข้องคือ 0

• สำหรับผมอยู่ในช่วง 0 ถึง p ทำ

  • สำหรับ j ในช่วง 0 ถึง q ทำ

    • ถ้า grid[i, j] เหมือนกับ '*' แล้ว

      • row[i] :=row[i] + 1

      • col[j] :=col[j] + 1

  • สำหรับแต่ละ k,v ในแถว ทำ

    • ถ้า v เท่ากับ 1 แล้ว

      • x_coord :=k;

  • สำหรับแต่ละ k,v ใน col ทำ

    • ถ้า v เท่ากับ 1 แล้ว

      • y_coord :=k;

• ผลตอบแทน(x_coord + 1, y_coord + 1)

ตัวอย่าง

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

def get_missing_vertex(grid) :
   p = len(grid)
   q = len(grid[0])
   row = dict.fromkeys(range(p), 0)
   col = dict.fromkeys(range(q), 0)
   for i in range(p) :
      for j in range(q) :
         if (grid[i][j] == '*') :
            row[i] += 1
            col[j] += 1
   for k,v in row.items() :
      if (v == 1) :
         x_coord = k;
   for k,v in col.items() :
      if (v == 1) :
         y_coord = k;
   return (x_coord + 1, y_coord + 1)
grid = [".*.", "...", "*.*"]
print(get_missing_vertex(grid))

อินพุต

[".*.", "...", "*.*"]

ผลลัพธ์

(1, 3)