问题描述:

Consider a two-dimensional grid (the usual lattice in the plane). For my purposes, a *pattern* or *arrangement* is an assignment of the numbers 1 and 2 to some connected subset of the grid points. For example, the following shows three separate arrangements:

`.......1.....1....`

.222...2.....12...

.111...2.....2....

.222...22...12211.

.......1....11.1..

I say that a small pattern matches a large one if the small one can be rotated or reflected such that all of its numbers are smaller than the numbers in the larger one. For example, consider this pattern:

`......`

.1212.

....2.

......

It does NOT match the leftmost arrangement above because it can't be rotated or reflected to fit in a 3x3 square. It DOES match the middle arrangement because it can be rotated and reflected to fit underneath. It does NOT, however, match the rightmost arrangement because however it is rotated or reflected to fit in the rightmost arrangement, the numbers are larger in the small pattern than the large arrangement. (If any of my examples are unclear or you need more information, just ask away in the comments area. Some clarifications in advance: the pattern can't be stretched, and it can't be rotated so it's diagonal with respect to the grid. That means there are four rotations and four reflections total, each of which can be translated.)

I am wondering about the following questions:

How can I quickly test if a small pattern matches a large arrangement?

Suppose I have a lot of small patterns. Can I pre-process them somehow to quickly tell if

*at least one*of them matches an arrangement?

I suppose it'd be cool if a solution solves a more general problem (like arbitrary numbers -- not just 1 and 2 -- or allowing disconnected shapes), but I really only care about the case above. Thanks.

2D convolution.

(complexity is n*Log(n) where n in number of elements) and might be good for larger matrices.

Make both matrices matching and non matching same size.

Test for each number seperatly.
Example - cheking number k
In serchung matrix (bigger) set numbers >= k on 0 other values on 1

In patteren matrix set values <= k on 1 other set on 0

Where the result of convolution is 0 is hit and match

Check for each rotation and reflexion (8 total)

That mean that general comlexity is k*n*log(n) where k is number of numbers (in your case 2) and n number of elements of bigger matrix)

您可能感兴趣的文章：

- Not all embedded Youtube videos play on iPhone app
- multithreading - General - Number of threads in thread pool
- sql - Using ruby with databases, but without rails
- c# - What's the best way to store/retrieve data for a desktop without using a database?
- Changing text appearance in Emacs: overlays work, text properties don't
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**