ბინარული სუდოკუ

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2011/12, NOV, GOLD


ჯონის ძროხებს უყვართ სუდოკუს თავისებური ვერსიის თამაში. ისინი იყენებენ სტანდარტულ 9 x 9 ცხრილს 3 x 3 ქვეცხრილებით. ამავე დროს ძროხების სუდოკუ ბინარულია: 000 000 000 001 000 100 000 000 000 000 110 000 000 111 000 000 000 000 000 000 000 000 000 000 000 000 000 ბინარული სუდოკუს მიზანია უმცირესი რაოდენობის უჯრების შეცვლით იმის მიღწევა, რომ ცხრავე სვეტში, ცხრავე სტრიქონში და ცხრავე ქვეცხრილში მიიღონ 1-ის ლუწი რაოდენობა. ზემოთ მოყვანილი მაგალითისთვის არსებობს 3-სვლიანი დასაშვები ამოხსნა: 000 000 000 001 000 100 001 000 100 000 110 000 000 110 000 000 000 000 000 000 000 000 000 000 000 000 000 ბინარული სუდოკუს მოცემული საწყისი კონფიგურაციისთვის განსაზღვრეთ მიზნისკენ მიმავალი სვლების მინიმალური რაოდენობა. ერთი სვლა ცხრილის ერთ უჯრის შეცვლას ნიშნავს. შემავალი მონაცემების ფორმატი: * სტრიქონები 1..9: ყოველი სტრიქონი მოიცავს 9 ციფრიან ბინარულ სტრიქონს, რომლებიც განსაზრვრავე თამიშის საწყის კონფიგურაციას. გამომავალი მონაცემების ფორმატი: * სტრიქონი 1: სვლების მინიმალური რაოდენობა, რომელთა შედეგად ყველა სტრიქონში, ყველა სვეტში და 9 ქვეცხრილში ერთიანობის რაოდენობა გახდება ლუწი.




მაგალითები

შესატანი მონაცემები
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება