This page is still under construction.

Parts of this page are still being built. What you see may change.

Antibody Recognition

Interview

Time limit1sMemory limit1024 MB

Summary
Given two grids, decide whether the second can result from picking one start cell, flooding its monochromatic connected component, and repainting that whole component one color.
Level

Medium6 of 10

Topics
BFS, DFS, Graph, Implementation
Solved
No attempts yet

Problem

VUNO develops Medical AI solutions that help medical experts make decisions, using artificial intelligence trained with big data and deep learning.

VUNO recently developed a powerful new imaging technique called SP. With this technique, human tissue is represented as a grid, and each cell of the grid is assigned a single data value that compresses various analysis results for that part. VUNO wants to study a new antibody called CPCU-1202 using the SP imaging technique.

When the CPCU-1202 vaccine is injected into tissue, an antibody is created in one of the grid cells. If there is a cell that is adjacent up, down, left, or right and has the same data value as the cell the antibody currently occupies, the antibody spreads to that cell. This process repeats until the antibody can no longer spread, at which point the antibody is fully absorbed into the tissue. As a result, the data values of all cells the antibody spread to are updated to some single identical value. It is possible that this updated value happens to equal the original data value.

VUNO's research data consists of a pair: the imaging result before the vaccine is injected into one tissue, and the imaging result after the vaccine is injected. Given the two imaging results, write a program that determines whether the vaccine injected into this tissue could be the CPCU-1202 vaccine.

(a) Before the vaccine is injected(b) CPCU-1202 administered(c) The antibody is being absorbed(d) After the vaccine is injected
Figure B.1: The CPCU-1202 vaccination process

Input

The first line gives two integers NN and MM, the size of the SP imaging result. (1≤N,M≤301 \le N, M \le 30) This means the imaging result is a grid with NN rows and MM columns.

The next NN lines give the imaging result before the vaccine is injected. Each line contains MM integers between 11 and 1 0001\ 000, separated by spaces. The jj-th number on the ii-th line is the data value of the cell at row ii, column jj of the imaging result.

The next NN lines give the imaging result after the vaccine is injected, in the same format as above.

Output

If the vaccine applied to the subject could be the CPCU-1202 vaccine, print YES. Otherwise, print NO.

Examples5

  1. Example 1

    Input
    4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
4 4 4 1
4 4 1 3
4 1 3 3
1 3 3 3
    Expected output
    YES

  2. Example 2

    Input
    4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
    Expected output
    YES

  3. Example 3

    Input
    4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
2 2 2 1
2 2 2 3
2 1 3 3
1 3 3 3
    Expected output
    YES

  4. Example 4

    Input
    4 4
2 2 2 1
2 2 1 2
2 1 2 2
1 2 2 2
3 3 3 1
3 3 1 3
3 1 3 3
1 3 3 3
    Expected output
    NO

  5. Example 5

    Input
    3 5
1 1 1 3 3
1 1 2 3 3
1 1 2 2 4
1 1 1 4 4
1 1 2 4 4
1 1 2 2 4
    Expected output
    YES