二維字符串的匹配以及對于題目特殊條件的處理

算法分析

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

一個簡單的做法是直接進行將每一幅星圖?p_i?與星空圖?s?進行模版匹配。

for?i?=?1?..?K
????exist[i]?=?false???????//?假設星圖p_i不在星空圖s上
????for?sx?=?1?..?N
????????for?sy?=?1?..?M????//?枚舉星空圖s的坐標作為匹配的左上角
????????????flag?=?true????//?假設匹配是成功的
????????????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的位置有星星，而星空圖s沒有
????????????????????end?if
????????????????end?for
????????????end?for
????????????if?(flag)?exist[i]?=?true;
????????end?for
????end?for
end?for

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

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

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

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

也即是說，對于一個星圖?p_i?我們實際關心的位置只有20個，也只需要關心這20個位置。

因此我們不妨將這20個星星的位置與左上角的相對坐標記錄下來，進行匹配時只對這20個位置進行匹配：

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???????//?假設星圖p_i不在星空圖s上
????for?sx?=?1?..?N
????????for?sy?=?1?..?M????//?枚舉星空圖s的坐標作為匹配的左上角
????????????flag?=?true????//?假設匹配是成功的
????????????for?j?=?1?..?the?number?of?stars
????????????????//?offset[i][j]?=?{x,?y}?表示第i個星圖第j顆星星相對于左上角的偏移量
????????????????if?(s[?sx?+?offset[i][j].x?][?sy?+?offset[i][j].y?]?!=?'#')
????????????????????flag?=?false????//?星圖p_i的位置有星星，而星空圖s沒有
????????????????end?if
????????????end?for
????????????if?(flag)?exist[i]?=?true;
????????end?for
????end?for
end?for

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

由于星圖十分稀疏，大部分星圖?p_i?在進行第一個星星匹配時就會失敗，因此該算法能夠通過全部的測試點。