lodhi
BAN USER- 0of 0 votes
AnswerYou are given a rectangular grid with 2 rows and N columns. The top row is labeled 1 and the bottom row is labeled 2. The columns are labeled from 1 to N in increasing order. Each cell in the grid contains a single character.
- lodhi in United States
Consider a hamiltonian walk in this grid. Meaning, pick a starting cell, say (i,j), and consider a path that starts from (i,j) and goes through every cell in the grid exactly once. Note that you can only walk to adjacent cells, or cells that you share a common edge with. There may be several such paths. Let us concatenate the characters in the order in which the cells are visited during a walk. The string formed can be called the string for the walk.
Among all the possible walks, and their respective strings, find out the lexicographically smallest string. We know that the length of the strings are all the same - to be precise, 2N. Thus, the lexicographically smallest string is simply the alphabetically smallest string if you compare the characters from left to right.
Input
The first line of input contains a number T, the number of test cases. Then follow T test cases. Each test case contains 3 lines. The first line contains the number N, the number of columns in the grid. It is well known of course that the grid contains 2 rows. The next two lines contain the description of the grid in the form of two strings; the string of N characters in row 1 from left to right and the string of N characters in row 2 from left to right, respectively. Each character will be a lowercase english letter.
Output
Output a single line for each test case. The line must contain a string with 2N characters. This string should be the lexicographically smallest string for some hamiltonian walk in the grid.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 10
Sample Input
2
3
abc
def
10
ababaaabab
bababababa
Sample Output
abcfed
aaababababababababab
Explanation
In the first test the possible strings are { abcfed, adebcf, adefcb, badefc, bcfeda, cbadef, cfedab, cfebad, dabcfe, dabefc, defcba, edabcf, efcbad, fedabc, fcbade, fcbeda }. The smallest string is abcfed.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersYou are given a grid with R rows and C columns. You are also given a robot which is very small and can be placed on the grid - to walk around in the grid. You will place the robot at some starting cell of your choosing. You will give the robot an initial direction. Then, when you start the robot, it will walk in the given direction till it gets out of the grid or encounters a "turn" cell in the grid.
- lodhi in United States
Each cell in the grid is either empty (depicted by '.') or a turn cell (depicted by 'r' or 'l'). When the robot encounters a turn cell with 'r', it will turn right on that cell. Note that this turn will be relative to the direction in which the robot is moving. Similarly, when the robot encounters a turn cell with 'l', it will turn left on that cell. The examples and explanations clarify this.
The robot will eventually leave the grid or enter a loop. You wish to choose a start point and direction for the robot such that it visits the maximum number of unique cells. Note that the start point you select must be an empty cell.
Print the maximum number of unique cells the robot will visit when you choose such a starting point.
Input
The first line of input contains a number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains two integers R and C. On the next R lines are exactly C characters each. Each character is either '.', 'r' or 'l'.
Output
For each test case, output a single number on a line by itself. This number should be the maximum number of unique cells the robot can visit if you place it optimally.
Constraints
1 ≤ T ≤ 20
1 ≤ R ≤ 20
1 ≤ C ≤ 20
Attention
The constraints are designed such that O(R*R*C*C) solutions will pass.
Sample Input
3
3 5
.....
...r.
...r.
2 2
..
..
1 5
.r...
Sample Output
8
2
4
Explanation
We will assume that the rows are labeled from 1 to R from top to bottom and columns are labeled from 1 to C from left to right.
In the first test case the optimal choice is to keep the robot at 2,1 facing east. The robot will move as 2,1 - 2,2 - 2,3 - 2,4 and then turn right, facing south. The robot will then move as 2,4 - 3,4 and then turn right, facing west. The robot will then move as 3,4 - 3,3 - 3,2 - 3,1 and then leave the grid. The robot touched 8 unique cells.
In the second test case you cannot optimise robot placement. No matter what you do, you can only touch 2 different cells.
In the third test case the optimal choice is to place the robot on 1,5 facing west.| Report Duplicate | Flag | PURGE
Can you please post code for this problem ?
- lodhi November 30, 2015