[HackerRank]棋盤搜尋(The Grid Search)

題目描述

給一個由0~9數字組成的二維陣列,接著要使用二維的樣本嘗試在這個陣列中搜尋符合樣本的數字

舉例來說,下面是一個二維陣列的圖形G:

1234567890
0987654321
1111111111
1111111111
2222222222

假設我們要尋找的二維陣列樣本P是:

876543
111111
111111

如果我們掃描原本的圖形G,我們可以發現從第二列到第四列的第三行到第八行,符合樣本P。因此可以說樣本P在圖形G裡面。

原題網址

https://www.hackerrank.com/challenges/the-grid-search

輸入格式

第一行為測試資料的數量T,範圍在1到5之間(包含1和5)。
接下來的T組資料的每個第一行為圖形G列數R和行數C
再來的R行輸入所有列的圖形資料。
接著輸入樣本P的列數r和行數c
再來的r行輸入所有列的樣本資料。
R、r、Cc的範圍在1到1000之間(包含1和1000),且r不超過R,c不超過C

輸出格式

如果樣本P存在於圖形G,輸出「YES」,否則輸出「NO」。

範例輸入

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

範例輸出

YES
NO

額外解釋

第一組資料可以在圖形G內找到樣本P:

7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137

第二組資料無法在圖形G內找到樣本P。

解題概念

在這題目中,由於二維陣列資料量很大(長度可達1000x1000),因此必須使用一個快速的方法來解決這個問題。

要如何用比較快的方法來找出樣本P是否在圖形G裡面呢?首先我們可以先找出樣本P的第一列在圖形G裡的位置,把圖形G的一列作為一段文字,樣本P的第一列當作是要在這段文字內尋找的字串。我們可以透過字串搜尋,來找出樣本P的第一列在圖形G的某列出現的所有位置。接著再比較樣本P的第二列至最後一列,是否都符合圖形G對應的位置。

由於可能要進行很多次的字串搜尋,在此筆者使用了Boyer-Moore-MagicLen這個字串演算法來提升搜尋速度。有關Boyer-Moore-MagicLen的說明可以參考這篇:

https://magiclen.org/boyer-moore-magiclen/

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章