oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

magicwand Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

magicwand.html

Problem Description

Rar the Cat has found a greyscale picture H by W pixels wide. Each pixel is a value between 0 and 1023 (inclusive).

Rar the Cat wants to edit the photo but is too lazy. He wants you to code the 'Magic Wand' feature.

The 'Magic Wand' will start at pixel (X, Y) with a threshold T, that is the Xth pixel from the top and Yth pixel from the left. It will then propagate in 4 directions (up/down/left/right), selecting pixels whose value is not more than T different from the starting pixel (X, Y). A pixel will only be selected if it is adjacent to another selected pixel, in addition to the constraint of values.

At the end of the day, Rar the Cat wants to know which pixels are selected by printing a H by W grid of 0 and 1s. '0' will denote an unselected pixel while '1' will denote a selected pixel.

Limits

For all testcases, 0 < X ≤ H, 0 < Y ≤ W, 0 ≤ T ≤ 1023.

Subtask 1 (32%): H = 1, 1 ≤ W ≤ 500.

Subtask 2 (33%): 1 ≤ H, W ≤ 500, each pixel will be either 0 or 1.

Subtask 3 (35%): 1 ≤ H, W ≤ 500.

Subtask 4 (0%): Sample Testcases.

Input

The first line of input will contain five integers, H, W, X, Y followed by T. X and Y are 1-indexed.

There will be H lines containing W integers each. Each integer will be between 0 and 1023, representing the value of the pixel.

Output

The output should contain H lines with W characters each. Each character should either be a '0' or '1', indicating whether the pixel is selected or not.

Sample Testcase 1

Input

3 3 2 2 1
1 3 4
2 0 1
3 1 2

Output

000
011
010

Explanation

The 'Magic Wand' operation starts at cell(2, 2), which corresponds to the centre pixel with value 0.

The 2 adjacent '1's are then selected as they are adjacent to the starting cell and their difference to the starting cell is not more than 1.

Sample Testcase 2

Input

7 9 3 7 2
3 4 4 6 3 9 4 8 2
2 3 4 9 5 2 1 2 0
0 3 4 6 9 2 3 8 1
2 3 5 7 8 3 2 8 1
0 9 3 8 5 6 8 2 0
0 5 6 4 6 5 4 2 3
1 2 3 4 5 6 7 8 9

Output

000010100
000011110
000001100
000001100
000000000
000000000
000000000

Explanation

The 'Magic Wand' operation starts at cell(3, 7), which corresponds to the pixel with value 3.

Hence, pixels between 1 and 5 that are adjacent to another selected cell, will be selected.

Sample Testcase 3

Input

7 9 3 7 3
3 4 4 6 3 9 4 8 2
2 3 4 9 5 2 1 2 0
0 3 4 6 9 2 3 8 1
2 3 5 7 8 3 2 8 1
0 9 3 8 5 6 8 2 0
0 5 6 4 6 5 4 2 3
1 2 3 4 5 6 7 8 9

Output

111110101
111011111
111101101
111001101
101011011
111111111
111111000

Explanation

The grid is the same as Sample Testcase 2.

The 'Magic Wand' operation starts at cell(3, 7), which corresponds to the pixel with value 3.

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
132151s32MBMinimum
233101s32MBMinimum
335761s32MBMinimum
4031s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o magicwand -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.