1164castle觀察城堡地圖統(tǒng)計(jì)

1、城堡要求：觀察城堡地圖，統(tǒng)計(jì)1、總共的房間數(shù)2、最大房間的面積競(jìng)賽書 P2IOI 1994 Day1 Problem 2Online Judge 1164分析統(tǒng)計(jì)問(wèn)題，解題的關(guān)鍵在于：一、設(shè)計(jì)一種合理的數(shù)據(jù)結(jié)構(gòu)描述問(wèn)題二、統(tǒng)計(jì)效率問(wèn)題描述定義：點(diǎn)： 城堡中的格直接連接：相鄰且公共邊非墻連接：直接連接或經(jīng)由其他點(diǎn)直接連接房間：相互連接的若干點(diǎn)的集合房間的面積：房間中點(diǎn)的個(gè)數(shù)優(yōu)點(diǎn)：1、每個(gè)點(diǎn)對(duì)應(yīng)輸入數(shù)據(jù)的一個(gè)數(shù)字2、直接連接可以根據(jù)一個(gè)點(diǎn)的狀態(tài)計(jì)算出來(lái)不需要預(yù)處理統(tǒng)計(jì)算法：1、將所有點(diǎn)的狀態(tài)標(biāo)記為“未知”2、遍歷所有點(diǎn)如果遇到的點(diǎn)為“未知”則將該點(diǎn)拓展為一個(gè)房間（拓展過(guò)程中會(huì)將拓展出的點(diǎn)標(biāo)記為屬于

2、相應(yīng)的房間）拓展完成后進(jìn)行相應(yīng)的統(tǒng)計(jì)拓展算法：初始化：設(shè)置open、close兩個(gè)空點(diǎn)集將種子置入open集計(jì)算：while(open非空)從open中取出一點(diǎn)a,置入close檢查與a直接連接的點(diǎn)b(最多四個(gè))if (b不屬于open且b不屬于close)then 將b置入open時(shí)間效率:每個(gè)點(diǎn)最多被訪問(wèn)5次：上下左右點(diǎn)的直接連接和主程序的遍歷每次訪問(wèn)要檢測(cè)是否屬于open或close集所需時(shí)間為：O（城堡面積） (點(diǎn)集隨機(jī)訪問(wèn)時(shí)間）每個(gè)點(diǎn)都進(jìn)open、close集各一次，出open 集一次，所需時(shí)間為O（城堡面積）*（點(diǎn)集順序訪問(wèn)時(shí)間）所以總的時(shí)間效率為：O（城堡面積）*（點(diǎn)集順序訪問(wèn)時(shí)間+點(diǎn)集隨機(jī)訪問(wèn)時(shí)間）注：我用的點(diǎn)集實(shí)現(xiàn)了常數(shù)級(jí)的兩種訪問(wèn)（見(jiàn)代碼）空間效率每個(gè)點(diǎn)的描述 O（城堡面積）每個(gè)點(diǎn)的狀態(tài) O（城堡面積）Open、Close 兩集合o（城堡面積）總的空間效率O（城堡面積）技巧：Close集不用保存，因?yàn)橐?/p>