Gallery Walk Matrix Problem

Gallery Walk Matrix Problem — ExecCode Hard DSA Practice

Solve the Gallery Walk Matrix problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A directed gallery graph: count walks of length exactly k from src to dst. If A is the adjacency matrix (parallel edges add), A^k[src][dst] is the answer. Matrix exponentiation computes that in O(n^3 log k). Edges [u, v] are directed (u→v). Return the number of walks. k = 0 is 1 if src = dst else 0. You are given: n — rooms edges — directed k — steps src — start dst — end Return number of walks. Walks may visit nodes more than once.

Examples

Input {'n': 2, 'edges': [[0, 1], [1, 0]], 'k': 2, 'src': 0, 'dst': 0}; Output 1. Input {'n': 2, 'edges': [[0, 1], [1, 0]], 'k': 0, 'src': 0, 'dst': 1}; Output 0. Input {'n': 1, 'edges': [[0, 0]], 'k': 3, 'src': 0, 'dst': 0}; Output 1

Constraints

Parallel edges multiply choices Self-loops allowed

Practice Gallery Walk Matrix free on ExecCode. Browse DSA problems, topic map, and placement guides.