首页 > 代码库 > Hackerrank--Lexicographic paths

Hackerrank--Lexicographic paths

2024-07-19 19:18:34   217人阅读

题目链接

Krishnakant is standing at (0,0) in the Cartesian plane. He wants to go to the point (N,M) in the same plane using only horizontal and vertical moves of 1 unit. There are many ways of doing this, and he is writing down all such ways. Every way will comprise of few H moves and few V moves. i.e. moves in horizontal and vertical direction respectively. For example, if we want to go to point (2,2) from point (0,0), HVHV is one of the possible ways.

Given the value of K, he wants to know lexicographically Kth smallest way of going to (N,M) from (0,0).

Input Format
The first line contains an integer T , i.e., number of test cases. 
Next T lines will contain integers N,M and K.

Output Format
For each test case, print lexicographically Kth smallest path.

Constraints
1≤T≤100000 
1≤N≤10 
1≤M≤10 
0≤K<number of paths

Sample Input

22 2 22 2 3

Sample Output

HVVHVHHV

Explanation

All the paths of going to (2,2) from (0,0) in lexicographically increasing order:

0.HHVV
1.HVHV
2.HVVH
3.VHHV
4.VHVH
5.VVHH

这题WA的我晕头转向。。题水人更水啊。
题目意思就是给出三个数，n, m, k，问从坐标系中的(0, 0)点走到(n, m)点的字典序第ｋ小的路径是什么。
每次只能向右或者向下走一步，水平走记为‘H‘, 垂直走记为‘V‘。
这题并不是难题。但是由于不太喜欢或者说不太擅长处理坐标系相关的题目，WA了十几次。
以后做这种题目还是老老实实的画坐标系吧。
Accepted Code:
 1 #include <cassert> 2 #include <iostream> 3 #include <string> 4 #include <cstring> 5 #include <cstdio> 6 #include <cstdlib> 7 using namespace std; 8  9 int dp[15][15], T, N, M, K;10 11 int main(void) {12     memset(dp, 0, sizeof(dp));13     for (int i = 9; i >= 0; i--) dp[i][10] = 1;14     for (int j = 9; j >= 0; j--) dp[10][j] = 1;15     for (int i = 9; i >= 0; i--) for (int j = 9; j >= 0; j--) dp[i][j] = dp[i + 1][j] + dp[i][j + 1];16     ios::sync_with_stdio(false);17     cin >> T;18     while (T--) {19         cin >> N >> M >> K;20         assert(N <= 10 && M <= 10 && N >= 1 && M >= 1);21         K++;22         string ans = "";23         int x = 10 - N, y = 10 - M;24         assert(K <= dp[x][y]);25         for (int i = 0; i < N + M; i++) {26             if (x == 10) {27                 ans += ‘V‘;28                 y++; continue;29             } else if (y == 10) {30                 ans += ‘H‘;31                 x++; continue;32             }33             if (dp[x + 1][y] < K) {34                 ans += ‘V‘;35                 K -= dp[x + 1][y];36                 y++;37             } else {38                 ans += ‘H‘;39                 x++;40             }41         }42         cout << ans << endl;43     }44     return 0;45 }

 

Hackerrank--Lexicographic paths


联系
我们