You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).
Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.
The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.
Example 1:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0 Output: [[0,0],[0,1]] Explanation: The distances from (0, 0) to other cells are: [0,1]
Example 2:
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1 Output: [[0,1],[0,0],[1,1],[1,0]] Explanation: The distances from (0, 1) to other cells are: [0,1,1,2] The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
Example 3:
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2 Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]] Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3] There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
Constraints:
1 <= rows, cols <= 1000 <= rCenter < rows0 <= cCenter < colsprogram main
implicit none
integer :: row, col, rCenter, cCenter
integer, allocatable :: dist(:, :)
integer :: i, j
! Example 1
row = 1
col = 2
rCenter = 0
cCenter = 0
call solve(row, col, rCenter, cCenter, dist)
write(*, "(A)") "Example 1:"
do i = 1, size(dist, 1)
write(*, "(A, I0, A, I0)") "[", dist(i, 1), ",", dist(i, 2), "]"
end do
! Example 2
row = 2
col = 2
rCenter = 0
cCenter = 1
call solve(row, col, rCenter, cCenter, dist)
write(*, "(A)") "Example 2:"
do i = 1, size(dist, 1)
write(*, "(A, I0, A, I0)") "[", dist(i, 1), ",", dist(i, 2), "]"
end do
! Example 3
row = 2
col = 3
rCenter = 1
cCenter = 2
call solve(row, col, rCenter, cCenter, dist)
write(*, "(A)") "Example 3:"
do i = 1, size(dist, 1)
write(*, "(A, I0, A, I0)") "[", dist(i, 1), ",", dist(i, 2), "]"
end do
contains
subroutine solve(row, col, rCenter, cCenter, dist)
implicit none
integer, intent(in) :: row, col, rCenter, cCenter
integer, allocatable, intent(out) :: dist(:, :)
integer :: i, j
allocate(dist(row * col, 2))
do i = 1, row
do j = 1, col
dist((i-1)*col+j, 1) = i
dist((i-1)*col+j, 2) = j
end do
end do
dist = abs(dist - [/( (i-1)*col+j, j=1,col ),/)])
dist = sum(dist, dim=2)
dist = sort(dist, dim=1)
end subroutine solve
end program maintemp.f95:58:28:
58 | dist = abs(dist - [/( (i-1)*col+j, j=1,col ),/)])
| 1
Error: Syntax error in array constructor at (1)
temp.f95:60:8:
60 | dist = sum(dist, dim=2)
| 1
Error: Incompatible ranks 2 and 1 in assignment at (1)
temp.f95:62:30:
62 | dist = sort(dist, dim=1)
| 1
Error: Keyword argument requires explicit interface for procedure ‘sort’ at (1)
temp.f95:62:15:
62 | dist = sort(dist, dim=1)
| 1
Error: Function ‘sort’ at (1) has no IMPLICIT type
module distance_from_center
contains
function get_distances(rows, cols, rCenter, cCenter) result(distances)
implicit none
integer, intent(in) :: rows, cols, rCenter, cCenter
integer :: i, j
integer, dimension(rows*cols) :: distances
! Initialize distances array
distances = 0
! Calculate distances from (rCenter, cCenter) to all cells in the matrix
do i = 0, rows - 1
do j = 0, cols - 1
distances(i*cols + j + 1) = abs(i - rCenter) + abs(j - cCenter)
end do
end do
end function get_distances
end module distance_from_center
program main
use distance_from_center
implicit none
integer, parameter :: rows = 2, cols = 3, rCenter = 1, cCenter = 2
integer, dimension(rows*cols) :: distances
integer :: i
! Calculate distances from (rCenter, cCenter) to all cells in the matrix
distances = get_distances(rows, cols, rCenter, cCenter)
! Print distances
do i = 1, rows*cols
write (*,*) distances(i), "(", i, ",", i, ")"
end do
end program main
3 ( 1 , 1 )
2 ( 2 , 2 )
1 ( 3 , 3 )
2 ( 4 , 4 )
1 ( 5 , 5 )
0 ( 6 , 6 )
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def smallestFromLeaf(self, root: TreeNode) -> str:
if not root:
return "|"
s = chr(root.val + 97)
if not root.left and not root.right:
return s
left = self.smallestFromLeaf(root.left)
right = self.smallestFromLeaf(root.right)
return min(left, right) + s
We perform a post-order traversal of the tree. If the root is null, we return the largest possible lexicographically ordered string "|". If the root is a leaf (both left and right children are null), we return the character equivalent of the node value converted to the corresponding lowercase alphabet character.
We get the lexicographically smallest strings from both the left and right subtrees (if they exist) and add the current root value's character equivalent to the result. We use the min function to determine the lexicographically smaller string between the two.
Note that we add the current root value's character equivalent to the end of the result string, so that the result string starts with a leaf node and goes to the root node as the function returns. This keeps the lexicographically smaller strings at the beginning and correctly forms the lexicographically smallest string from leaf to root.
#include <climits>
#include <string>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
string smallestFromLeaf(TreeNode* root) {
if (!root) return "|";
string s(1, root->val + 'a');
if (!root->left && !root->right) return s;
string left = smallestFromLeaf(root->left);
string right = smallestFromLeaf(root->right);
return min(left, right) + s;
}
We perform a post-order traversal of the tree. If the root is null, we return the largest possible lexicographically ordered string "|". If the root is a leaf (both left and right children are null), we return the character equivalent of the node value converted to the corresponding lowercase alphabet character.
We get the lexicographically smallest strings from both the left and right subtrees (if they exist) and add the current root value's character equivalent to the result. We use the min function to determine the lexicographically smaller string between the two.
Note that we add the current root value's character equivalent to the end of the result string, so that the result string starts with a leaf node and goes to the root node as the function returns. This keeps the lexicographically smaller strings at the beginning and correctly forms the lexicographically smallest string from leaf to root.