diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/snakes_ladders.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/snakes_ladders.cpp')
-rw-r--r-- | other/snakes_ladders.cpp | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/other/snakes_ladders.cpp b/other/snakes_ladders.cpp new file mode 100644 index 0000000..160b473 --- /dev/null +++ b/other/snakes_ladders.cpp @@ -0,0 +1,47 @@ +// 909. Snakes and Ladders +#include "leetcode.h" + +typedef pair<int, int> pii; +class Solution { +public: + int snakesAndLadders(vvd & board) { + int rows = board.size(), cols = board[0].size(); + int target = rows * cols, r, c, p; + vector<int> visited(rows * cols + 1); // cells on board starting from 1 + priority_queue<pii, vector<pii>, greater<pii>> pq; + pq.push(make_pair(0, 1)); + visited[1] = true; + while (pq.size()) { + auto stepPos = pq.top(); + pq.pop(); + int s = stepPos.first / 1000 + 1; + for (int i = 1; i <= 6; i++) { + auto p = stepPos.second + i; + if (visited[p]) + continue; + visited[p] = true; + r = rows - (p - 1) / cols - 1; + c = (p - 1) % cols; + if ((rows - r - 1) % 2) + c = cols - c - 1; + int ladder = board[r][c]; + if (ladder > 0 && ladder <= target) + p = ladder; + if (p == target) + return s; + pq.push(make_pair(s * 1000 + 500 - p, p)); + } + } + return -1; + } +}; + +int main() { + Solution obj; + vvd board1 = {{-1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1}, + {-1, -1, -1, -1, -1, -1}, {-1, 35, -1, -1, 13, -1}, + {-1, -1, -1, -1, -1, -1}, {-1, 15, -1, -1, -1, -1}}; + vvd board2 = {{-1, -1}, {-1, 3}}; + cout << obj.snakesAndLadders(board1) << endl; // expect: 4 + cout << obj.snakesAndLadders(board2) << endl; // expect: 1 +} |