《Constellations》

小Hi最近愛上了星座，所以他買了一份星座圖。今天晚上小明拿著星座圖，對(duì)著夜空正在比較，他想知道現(xiàn)在夜空里能夠看到哪些星座。小Hi所處的位置是正對(duì)北方，星座圖也是正對(duì)北方繪制，所以在搜索星座的時(shí)候不需要旋轉(zhuǎn)星座圖。

算法分析

本題主要的考察點(diǎn)為二維字符串的匹配以及對(duì)于題目特殊條件的處理，和上一次比賽的《Lost in City》基本是相同的類型。

一個(gè)簡(jiǎn)單的做法是直接進(jìn)行將每一幅星圖?p_i?與星空?qǐng)D?s?進(jìn)行模版匹配。

for?i?=?1?..?K
????exist[i]?=?false???????//?假設(shè)星圖p_i不在星空?qǐng)Ds上
????for?sx?=?1?..?N
????????for?sy?=?1?..?M????//?枚舉星空?qǐng)Ds的坐標(biāo)作為匹配的左上角
????????????flag?=?true????//?假設(shè)匹配是成功的
????????????for?px?=?1?..?H
????????????????for?py?=?1?..?W
????????????????????if?(p_i[px][py]?==?'#'?&&?p_i[px][py]?!=?s[sx?+?px?-?1][sy?+?py?-?1])
????????????????????????flag?=?false????//?星圖p_i的位置有星星，而星空?qǐng)Ds沒有
????????????????????end?if
????????????????end?for
????????????end?for
????????????if?(flag)?exist[i]?=?true;
????????end?for
????end?for
end?for

該算法的時(shí)間復(fù)雜度為?O(KMNHW)。

對(duì)于給定的數(shù)據(jù)范圍：1≤K≤20, 1≤M,N≤1000, 1≤W,H≤100。在極限數(shù)據(jù)下顯然會(huì)超過時(shí)間限制，因此我們需要對(duì)算法進(jìn)行優(yōu)化。

在題目中，有一個(gè)我們沒有用上的條件：每個(gè)星圖?p_i?中包含的星星數(shù)量不超過20，整個(gè)星空?qǐng)Ds?的星星數(shù)量不超過5000。

要查詢一個(gè)星圖?p_i?是否存在，只需要知道這個(gè)星圖?p_i?上有星星的位置在星空?qǐng)D?s?上是否也有。而對(duì)于星圖?p_i?上空白的區(qū)域我們并不關(guān)心。

也即是說，對(duì)于一個(gè)星圖?p_i?我們實(shí)際關(guān)心的位置只有20個(gè)，也只需要關(guān)心這20個(gè)位置。

因此我們不妨將這20個(gè)星星的位置與左上角的相對(duì)坐標(biāo)記錄下來，進(jìn)行匹配時(shí)只對(duì)這20個(gè)位置進(jìn)行匹配：

for?i?=?1?..?K
????cnt?=?0
????for?px?=?1?..?N
????????for?py?=?1?..?M????
????????????if?(p_i[px][py]?==?'#')????????????//?記錄星圖p_i中的每一顆星星
????????????????cnt?=?cnt?+?1
????????????????offset[i][?cnt?].x?=?px?-?1????//?x軸偏差量
????????????????offset[i][?cnt?].y?=?py?-?1????//?y軸偏差量
????????????end?if?
????????end?for
????end?for
end?for?

for?i?=?1?..?K
????exist[i]?=?false???????//?假設(shè)星圖p_i不在星空?qǐng)Ds上
????for?sx?=?1?..?N
????????for?sy?=?1?..?M????//?枚舉星空?qǐng)Ds的坐標(biāo)作為匹配的左上角
????????????flag?=?true????//?假設(shè)匹配是成功的
????????????for?j?=?1?..?the?number?of?stars
????????????????//?offset[i][j]?=?{x,?y}?表示第i個(gè)星圖第j顆星星相對(duì)于左上角的偏移量
????????????????if?(s[?sx?+?offset[i][j].x?][?sy?+?offset[i][j].y?]?!=?'#')
????????????????????flag?=?false????//?星圖p_i的位置有星星，而星空?qǐng)Ds沒有
????????????????end?if
????????????end?for
????????????if?(flag)?exist[i]?=?true;
????????end?for
????end?for
end?for

offset數(shù)組需要進(jìn)行預(yù)處理，花費(fèi)的時(shí)間為?O(KHW)，匹配的算法時(shí)間復(fù)雜度為?O(KMN)。

由于星圖十分稀疏，大部分星圖?p_i?在進(jìn)行第一個(gè)星星匹配時(shí)就會(huì)失敗，因此該算法能夠通過全部的測(cè)試點(diǎn)。