Chef and Finding Direction
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a grid of size N * N with its rows numbered from 1 to N, and the columns also numbered from 1 to N. The cell at the ith row and the jth column is cell (i,j). From cell (i,j), you can go in one of the four directions U L D R (corresponding to up, left, down, right) to cells (i-1,j), (i,j-1), (i+1,j), (i,j+1) respectively, and of course you cannot go outside of the grid. However, with each cell, Chef is only allowed to go in some of the four directions (at least one), which is given by a string directs[i][j] containing only the characters U L D R denoting the directions Chef can go from cell (i,j).
Now, Chef wants to choose exactly one direction to go from each cell, so that from any cell in the grid, he can come back to same cell by following the chosen directions of the cells. Please help him!
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of the grid.
N lines follow. Each line contains N space-separated strings denoting the given directions for that cell. The jth string in the ith line is directs[i][j].
For each test case, output a single line containing "YES" (without quotes) if for each cell Chef can choose one and only one direction to go so that from every cell Chef can go back to that cell using chosen directions, "NO" (without quotes) otherwise.
If the answer is "YES", then you must print the chosen directions in the next N lines. Each line will contain N strings. The jth string in the ith line must consist of a single character: the direction chosen for cell (i,j).
- 1 ≤ T ≤ 50
- 2 ≤ N ≤ 150
- 1 ≤ length directs[i][j] ≤ 4
SubtasksSubtask #1: (10 points)
- 2 ≤ N ≤ 5
- 1 ≤ length directs[i][j] ≤ 2
- 2 ≤ N ≤ 12
- 2 ≤ N ≤ 50
Subtask #4: (40 points)
- Original constraints
Input: 2 2 RD D UR UL 3 RD LR DL RU LU LDU U UL L Output: YES R D U L NO
Example case 1. Chef can keep the direction R for cell (1, 1), D for (1, 2), U for (2, 1) and L for (2, 2). Then he can go (1,1) -> (1,2) -> (2,2) -> (2,1) -> (1,1). It means that from any cell he always can go back to that cell.
Example case 2. There is no way to keep only 1 direction for each cell to satisfy the condition.
|Tags||dec16, hamiltonian, hopcroft-karp, lexman, matching, maxflow|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.