Queen Toqquşmaları
Kompüter elmləri tələbələri şahmat taxtasında vəzirlərin yerləşdirilməsi ilə bağlı çox vaxt sərf ediblər. Şahmat taxtasında iki vəzir eyni sıra, sütun və ya diaqonaldadırsa və aralarında heç bir fiqur yoxdursa, onlar toqquşurlar. Müxtəlif ölçülü kvadrat taxtalar və vəzir sayı nəzərə alınır. Məsələn, Şəkil 1-də 7x7 taxtada 7 vəzir heç bir toqquşma olmadan yerləşdirilib. Şəkil 2-də 5x5 taxtada 5 vəzir və 4 toqquşma var. Şəkil 3-də ənənəvi 8x8 taxtada 7 vəzir və 5 toqquşma var.
nxn taxtasında vəzir mövqeləri Kartes koordinatlarında (x, y) verilir, burada x sütun nömrəsidir, 1-dən n-ə qədər, və y sıra nömrəsidir, 1-dən n-ə qədər. Müxtəlif mövqelərdə olan (x_1, y_1) və (x_2, y_2) vəzirlər eyni diaqonaldadırlar, əgər (x_1- x_2) və (y_1- y_2) eyni böyüklüyə malikdirsə. Onlar eyni sıra və ya sütundadırlar, əgər x_1= x_2 və ya y_1= y_2-dirsə, müvafiq olaraq. Bu halların hər birində, əgər eyni diaqonalda, sırada və ya sütunda birbaşa aralarında başqa vəzir yoxdursa, vəzirlər toqquşurlar. Məsələn, Şəkil 2-də toqquşmalar (5, 1) və (4, 2), (4, 2) və (3, 3), (3, 3) və (2, 4), və nəhayət (2, 4) və (1, 5) arasında baş verir. Şəkil 3-də toqquşmalar (1, 8) və (4, 8), (4, 8) və (4, 7), (4, 7) və (6, 5), (7, 6) və (6, 5), və nəhayət (6, 5) və (2, 1) arasında baş verir. Sizin vəzifəniz vəzir toqquşmalarını saymaqdır.
Çox hallarda vəzirlər müəyyən bir naxışda yerləşdirilir. Məsələn, Şəkil 1-də (1,1), (2, 3), (3, 5), və (4, 7) mövqelərində 4 vəzir bir xətt üzrə yerləşdirilib. Bu vəzirlərin hər biri (1, 1) mövqeyindən sonra əvvəlkindən bir sağda və 2 yuxarıdadır. (5, 2) mövqeyindən başlayan üç vəzir oxşar naxışa uyğun gəlir. Bu naxışları qeyd etmək, çox sayda vəzirin mövqelərini qısa şəkildə ifadə etməyə imkan verir.
Giriş verilənləri
Giriş birdən iyirmiyə qədər məlumat dəstindən ibarət olacaq, ardınca yalnız 0 olan bir sıra gələcək.
Məlumat dəstinin ilk sətri boşluqla ayrılmış müsbət tam ədədlər n g ehtiva edir, burada n n x n taxta ölçüsünü göstərir və g vəzirlərin təsvir ediləcək xətti naxışlarının sayıdır, burada n < 30000, və g < 250. Növbəti g sətir hər biri beş boşluqla ayrılmış tam ədəd ehtiva edir, k x y s t, k vəzirin (x + i*s, y +i*t) mövqelərində yerləşdirildiyi xətti naxışı təmsil edir, burada i = 0, 1, ..., k-1. k dəyəri müsbətdir. Əgər k 1-dirsə, onda s və t dəyərləri əhəmiyyətsizdir və 0 olaraq veriləcək. Bütün vəzir mövqeləri taxtada olacaq. Bütün xətti naxışlar arasında ümumi vəzir mövqelərinin sayı n-dən çox olmayacaq və bu vəzir mövqelərinin hamısı fərqli olacaq.
Çıxış verilənləri
Hər bir məlumat dəsti üçün yalnız vəzirlər arasında toqquşmaların sayını ehtiva edən bir çıxış sətri var.
Nümunə giriş məlumat dəsti Şəkillərdəki konfiqurasiyaya uyğundur.
Alqoritminizlə diqqətli olun, əks halda həlliniz çox uzun çəkə bilər.