Floodfill ©

300000

427276

209822

ទឹកជំនន់^©

ការណែនាំសម្រាប់ការលេងហ្គេម Floodfill

បញ្ហានៃការប្រើពណ៌ចំនួនតិចបំផុតដើម្បីដាក់ពណ៌ផែនទីមានប្រវត្តិយូរអង្វែងដូចដែលបានពន្យល់ជាឧទាហរណ៍ក្នុង អត្ថបទវិគីភីឌានេះ។ ទ្រឹស្តីបទដែលពណ៌ចំនួន 4 តែងតែគ្រប់គ្រាន់សម្រាប់ដាក់ពណ៌ផែនទីយន្តហោះបានល្បីថាជាទ្រឹស្តីបទគណិតវិទ្យាដ៏ធំដំបូងគេដែលអាចបញ្ជាក់បានតែដោយកុំព្យូទ័រប៉ុណ្ណោះ មិនមែនតាមរយៈភស្តុតាង "គណិតវិទ្យា" ដែលផលិតដោយមនុស្សនោះទេ។

មិនមានក្បួនដោះស្រាយដែលគេស្គាល់ថាតែងតែគូសផែនទីប្រកបដោយប្រសិទ្ធភាពនោះទេ។ ជាមួយ "ប្រកបដោយប្រសិទ្ធភាព" យើងមានន័យថា ប្រសិនបើចំនួនតំបន់ N មានទំហំធំខ្លាំង នោះចំនួននៃការព្យាយាមលាបពណ៌ដែលចាំបាច់នឹងកើនឡើងដូចជា N^k ដែល k ជាលេខដែលមិន អាស្រ័យលើ N ។ ម្យ៉ាងវិញទៀត សម្រាប់ក្បួនដោះស្រាយ "ប្រសិទ្ធភាព" ចំនួននៃការប៉ុនប៉ងកើនឡើងតែដូចជាពហុនាមនៃ N ប៉ុណ្ណោះ។ ផ្ទុយទៅវិញ ក្បួនដោះស្រាយការលាបពណ៌ដែលគេស្គាល់មានភាពស្មុគស្មាញដែលហៅថាអិចស្ប៉ូណង់ស្យែល ពោលគឺចំនួននៃការព្យាយាមអាស្រ័យលើ N ដូចជា 4^N ។

ប្រសិនបើគេត្រូវបានអនុញ្ញាតឱ្យប្រើ ៥ ឬ ៦ ពណ៌ ឬប្រសិនបើផែនទីត្រូវការតែ ២ ពណ៌ នោះក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាពនឹងត្រូវបានគេដឹង។

ឱកាសមួយទៀតដើម្បីទទួលបានវិធីសាស្ត្រមានប្រសិទ្ធភាពគឺត្រូវពិភាក្សានិងអនុវត្តតាមក្បួនដោះស្រាយដ៏មានប្រសិទ្ធិភាពមួយ។ វិធីសាស្រ្ត (ជាការណែនាំ) ដែលមានប្រសិទ្ធភាពលើករណីជាច្រើននឹងត្រូវពិភាក្សាដូចខាងក្រោម៖

សំណួរ៖ តើតំបន់ណាដែលត្រូវលាបពណ៌មុនគេ?

សំណួរ៖ តើជម្រើសពណ៌មួយណាដែលរើសបានតាមចិត្ត?

សំណួរ៖ តើត្រូវដាក់ពណ៌តំបន់ណាបន្ទាប់?

តំបន់បន្ទាប់ដែលយើងគួរដាក់ពណ៌គឺតំបន់ដែលនៅសល់ពណ៌តែមួយពណ៌គត់ដែលអាចដាក់បាន ដូចនេះយើងមិនត្រូវមានកំហុសក្នុងការដាក់ពណ៌តំបន់នេះទេ។ .
ចំនួននៃការព្យាយាមពណ៌គឺពិតជាតិចជាង 4^N (សាកល្បងពណ៌ទាំង 4 សម្រាប់តំបន់ N ទាំងអស់)។ ដូច្នេះចំនួននៃការព្យាយាមពណ៌នេះអាស្រ័យយ៉ាងសំខាន់ទៅលើចំនួនតំបន់ N ។ ដូច្នេះវាមានប្រយោជន៍ ប្រសិនបើការលាបពណ៌បំបែកផ្នែកពណ៌ស (គ្មានពណ៌) នៃផែនទីទៅជាផែនទីរងពណ៌សដែលផ្តាច់ដោយឡែក ដែលបន្ទាប់មកអាចត្រូវបានពណ៌ដោយខ្លួនឯង។ តំបន់ទាំងនេះមានតែ N₁ និង N₂ តំបន់ (N = N₁ + N₂) ដែលត្រូវការឥឡូវនេះច្រើនបំផុតត្រឹមតែ 4^N₁ + 4^N₂ ព្យាយាមដែលតិចជាង 4^N₁ & ដង; 4^N₂ = 4^N ព្យាយាម។
ប្រសិនបើអ្នកចង់រកចំនួនពណ៌តិចបំផុតដែលអាចដាក់ពណ៌លើផែនទីដែលឲ្យ នោះដំបូងអ្នកត្រូវពិនិត្យមើលចំនួន ២ ពណ៌ជាការគ្រប់គ្រាន់។ នេះអាចត្រូវបានធ្វើយ៉ាងមានប្រសិទ្ធិភាព។

ប្រសិនបើមានតែពីរពណ៌ A និង B ដែលត្រូវដាក់ តែតំបន់នោះមានពណ៌រួចហើយខុសពីពណ៌ដែលត្រូវដាក់ នោះគេត្រូវជួសជុល(ដាក់ពណ៌សារថ្មី)ចាប់ផ្តើមចេញពីជុំវិញចំនុចប្រសព្វ៖

វិធាននេះក៏មានប្រយោជន៍ចំពោះផែនទីដែលត្រូវប្រើ ៣ ពណ៌ ឬ ៤ ពណ៌ ដែរ ។ ឧទាហរណ៍ ប្រសិនបើតំបន់ទី ១ ខាងក្រោមបានដាក់ពណ៌ A នោះតំបន់ទី ២ និង ទី៤ ត្រូវតែដាក់ពណ៌ផ្សេង ហើយយើងមិនទាន់ដឹងថាត្រូវដាក់ពណ៌ណានៅឡើយទេ ប៉ុន្តែយើងដឹងថាការដាក់ពណ៌ A លើតំបន់ទី ៣ មិនបង្កលក្ខខណ្ឌបន្ថែមលើការដាក់ពណ៌តំបន់ទី ២ និងទី ៤ ទេ ពីព្រោះពួកវាសុទ្ធតែមានតំបន់ជិតខាងដែលមានពណ៌ A រួចហើយ។

រូបភាពទី ៣ បង្ហាញតែផ្នែកតូចមួយនៃផែនទីប៉ុណ្ណោះ ប៉ុន្តែវាអាចធ្វើឱ្យយល់ច្បាស់ដែលអាចយកទៅអនុវត្តសម្រាប់ផែនទីផ្សេងជាច្រើនទៀត។ ប្រសិនបើតំបន់ជិតខាងទាំងអស់នៃតំបន់ទី ៣ (តំបន់ទី ២ និងទី ៤ ក្នុងរូបភាពទី ៣) ក្នុងចំណោមនេះបើវាមានតំបន់ជិតខាងយ់ាងតិចមួយដែលមានពណ៌A (តំបន់ ១ នៅក្នុងរូបភាពទី ៣) នោះការដាក់ពណ៌ A លើតំបន់ទីដែរ មិនអាចជាកំហុសទេ។ មូលហេតុគឺថា ការដាក់ពណ៌ A លើតំបន់ពណ៌ទី ៣ មិនបង្កើតការរឹតត្បិតថ្មីលើតំបន់ជិតខាងទេពីព្រោះពួកគេត្រូវបានហាមឃាត់មិនឱ្យមានពណ៌ A រួចទៅហើយ។ ដូច្នេះ ប្រសិនបើនៅក្នុងដំណើរការដាក់ពណ៌បន្តបន្ទាប់ទៀត បង្ហាញឲ្យឃើញថាមានកំហុស (ដោយសារពណ៌ដែលត្រូវដាក់ជាន់ជាមួយពណ៌នៃតំបន់ជិតខាង) នោះគេត្រូវសាកល្បងដាក់ពណ៌ផ្សេងលើតំបន់ទី ៣ ជំនួសពណ៌ A វិញ។
ចុះបើតំបន់ទី ៣ ខាងលើក៏ជាតំបន់ជិតខាងតាមទិសអង្កត់ទ្រូងទៅនឹងតំបន់ផ្សេងទៀតដែរ ឧទាហរណ៍តំបន់ទី ៩ ដែលមានពណ៌ផ្សេងរួចទៅហើយ ឧទាហរណ៍ដូចជាពណ៌ B នោះតើតំបន់ទី ៣ គួរតែដាក់ពណ៌ A ឬ ពណ៌B? ដូចគ្នានេះដែរ គេត្រូវពិនិត្យមើលតំបន់ជិតខាងទាំងអស់របស់តំបន់ទី ៣ ថាតើពួកគេត្រូវបានហាមឃាត់មិនឱ្យដាក់ពណ៌ A ឬក៏ហាមឃាត់មិនឱ្យមានពណ៌ B ។ ប្រសិនបើមិនចូលករណីណាមួយនោះទេ ការដាក់ពណ៌លើតំបន់ទី៣ អាចត្រូវរង់ចាំសិន (ដាក់ពណ៌កន្លែងផ្សេងសិន) ។

ទឹកជំនន់©

ការណែនាំសម្រាប់ការលេងហ្គេម Floodfill

ទឹកជំនន់^©