In this HackerRank Clues on a Binary Path problem solution we have given a map of Neptune, help Logan and Veronica find and print the number of different paths of length D from house number 1 to the other houses in Neptune.
Problem solution in Java.
import java.io.*; import java.util.StringTokenizer; public class Solution { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); int n = in.nextInt(); int m = in.nextInt(); int d = in.nextInt(); if ( !(1 <= n && n <= 70) || !(0 <= m && m <= n * (n - 1)) || !(1 <= d && d <= 20)) throw new RuntimeException(); int[] x = new int[m]; int[] y = new int[m]; int[] w = new int[m]; for (int i = 0; i < m; ++i) { x[i] = in.nextInt(); x[i]--; y[i] = in.nextInt(); y[i]--; if (!(0 <= x[i] && x[i] < n) || !(0 <= y[i] && y[i] < n)) throw new RuntimeException(); w[i] = in.nextInt(); if (!(0 <= w[i] && w[i] <= 1)) throw new RuntimeException(); } int l = (d + 1) / 2; int[][] dp = new int[n][1 << l]; int[][] ndp = new int[n][1 << l]; for (int i = 0; i < n; ++i) for (int j = 0; j < (1 << l); ++j) dp[i][j] = ndp[i][j] = 0; dp[0][0] = 1; for (int i = 0; i < n; ++i) dp[i][0] |= 2; for (int c = 0; c < l; ++c) { for (int i = 0; i < m; ++i) { int u = x[i]; int v = y[i]; int b = w[i]; for (int t = 0; t < (1 << c); ++t) { ndp[u][(t << 1) | b] |= dp[v][t]; ndp[v][(t << 1) | b] |= dp[u][t]; } } if (c + 1 < l) { for (int i = 0; i < n; ++i) { for (int j = 0; j < (1 << (c + 1)); ++j) { dp[i][j] = ndp[i][j]; ndp[i][j] = 0; } } } } Boolean[] can = new Boolean[1 << d]; for (int i = 0; i < (1 << d); ++i) can[i] = false; int r = d - l; for (int v = 0; v < n; ++v) { for (int t = 0; t < (1 << r); ++t) { int c = (l == r ? ndp[v][t] : dp[v][t]); if ((c & 1) == 0) continue; for (int s = 0; s < (1 << l); ++s) { if ((ndp[v][s] & 2) > 0) can[(t << l) ^ s] = true; } } } int res = 0; for (int i = 0; i < (1 << d); ++i) if (can[i]) res++; out.println(res); out.close(); } } class InputReader { private final BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String nextLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(nextLine()); } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } }
Problem solution in C++.
#include <stdio.h> #include <algorithm> #include <cmath> #include <vector> #include <queue> using namespace std; #define pb push_back #define mp make_pair #define F first #define S second const int N = 99; const int L = 13; int n, m, l; bool used[(1 << 20) + 100]; bool canMake[N][(1 << 10) + 100]; bool f[N][N][L][(1 << 10) + 100]; vector< pair<int, int> > g[N]; int main() { scanf("%d%d%d", &n, &m, &l); for (int i = 1; i <= m; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); g[u].pb(mp(v, c)); g[v].pb(mp(u, c)); } queue<int> q_start, q_ver, q_len, q_mask; for (int i = 1; i <= n; i++) { f[i][i][0][0] = true; q_start.push(i); q_ver.push(i); q_len.push(0); q_mask.push(0); } int maxMoves = (l + 1) / 2; while (!q_start.empty()) { int start = q_start.front(); int ver = q_ver.front(); int len = q_len.front(); int mask = q_mask.front(); q_start.pop(); q_ver.pop(); q_len.pop(); q_mask.pop(); if (len == maxMoves) { continue; } for (int i = 0; i < (int)g[ver].size(); i++) { int to = g[ver][i].F; int bit = g[ver][i].S; int newMask = mask; if (bit == 1) { newMask += (1 << len); } if (f[start][to][len + 1][newMask] == false) { f[start][to][len + 1][newMask] = true; q_start.push(start); q_ver.push(to); q_len.push(len + 1); q_mask.push(newMask); } } } int maxMask = (1 << maxMoves); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int mask = 0; mask < maxMask; mask++) { if (f[i][j][maxMoves][mask]) { canMake[j][mask] = true; } } } } int lengthOfFirstPart = l - maxMoves; int maxMask2 = (1 << lengthOfFirstPart); for (int ver = 1; ver <= n; ver++) { for (int m1 = 0; m1 < maxMask2; m1++) { if (f[1][ver][lengthOfFirstPart][m1]) { for (int m2 = 0; m2 < maxMask; m2++) { if (canMake[ver][m2]) { used[(m1 << maxMoves) + m2] = true; } } } } } int ans = 0; int maxMaskOverall = (1 << l); for (int i = 0; i < maxMaskOverall; i++) { if (used[i]) { ++ans; } } printf("%dn", ans); return 0; }