Algorithm (Dynamic Programming)
- Let $f(i,j)$ denote the maximum score collected when reaching $(i,j)$ when starting from lower right corner. And $g(i,j)$ be the number of paths to reach $f(i,j)$ when starting from the lower right corner.
- Then we have $$f(i,j)=\begin{cases}
B_{ij} & \text{if }i=R-1\text{ and }j=C-1\\\\
\underset{(n,m)\in\text{neighbors}(i,j)}{\max}\{B_{ij}+f(m,n)\} & \text{else}
\end{cases},$$ and $$g(i,j)=\begin{cases}
1 & \text{if }i=R-1\text{ and }j=C-1\\\\
\underset{(n,m)\in\mathrm{neighbors}(i,j)}{\sum}g(n,m)\cdot\mathbb{I}(f(m,n)+B_{ij}=f(i,j)) & \text{else}
\end{cases}.$$ Note that
neighbors
represents the valid neighbors of $(i,j),$ and its implementation is trivial.
Code
namespace math::field {
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Z {
public:
using value_type = typename T::value_type;
constexpr static value_type mod() { return T::value; }
// constructors
constexpr Z() : value() {}
template <typename U> Z(const U& x) { value = normalize(x); }
template <typename U> static value_type normalize(const U& x) {
if (0 <= x and x < mod()) return value_type(x);
else if (x >= mod()) return value_type(x % mod());
else return value_type(x + mod());
}
Z& operator+=(const Z& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Z& operator-=(const Z& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
Z& operator++() { return *this += 1; }
Z& operator--() { return *this -= 1; }
Z operator++(int) { Z result(*this); *this += 1; return result; }
Z operator--(int) { Z result(*this); *this -= 1; return result; }
Z operator-() const { return Z(-value); }
Z& operator*=(const Z& rhs) { value = (value % mod() * rhs.value % mod()) % mod(); return *this; }
Z& operator/=(const Z& other) { return *this *= Z(inverse(other.value, mod())); }
const value_type& operator()() const { return value; }
template <typename U> explicit operator U() const { return static_cast<U>(value); }
template <typename U> Z& operator+=(const U& other) { return *this += Z(other); }
template <typename U> Z& operator-=(const U& other) { return *this -= Z(other); }
template <typename U> friend const Z<U>& abs(const Z<U>& v) { return v; }
template <typename U> friend bool operator==(const Z<U>& lhs, const Z<U>& rhs);
template <typename U> friend bool operator<(const Z<U>& lhs, const Z<U>& rhs);
template <typename U> friend std::istream& operator>>(std::istream& stream, Z<U>& number);
private:
value_type value;
};
template <typename T> bool operator==(const Z<T>& lhs, const Z<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Z<T>& lhs, U rhs) { return lhs == Z<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Z<T>& rhs) { return Z<T>(lhs) == rhs; }
template <typename T> bool operator!=(const Z<T>& lhs, const Z<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Z<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Z<T>& rhs) { return !(lhs == rhs); }
template <typename T> bool operator<(const Z<T>& lhs, const Z<T>& rhs) { return lhs.value < rhs.value; }
template <typename T> Z<T> operator+(const Z<T>& lhs, const Z<T>& rhs) { return Z<T>(lhs) += rhs; }
template <typename T, typename U> Z<T> operator+(const Z<T>& lhs, U rhs) { return Z<T>(lhs) += rhs; }
template <typename T, typename U> Z<T> operator+(U lhs, const Z<T>& rhs) { return Z<T>(lhs) += rhs; }
template <typename T> Z<T> operator-(const Z<T>& lhs, const Z<T>& rhs) { return Z<T>(lhs) -= rhs; }
template <typename T, typename U> Z<T> operator-(const Z<T>& lhs, U rhs) { return Z<T>(lhs) -= rhs; }
template <typename T, typename U> Z<T> operator-(U lhs, const Z<T>& rhs) { return Z<T>(lhs) -= rhs; }
template <typename T> Z<T> operator*(const Z<T>& lhs, const Z<T>& rhs) { return Z<T>(lhs) *= rhs; }
template <typename T, typename U> Z<T> operator*(const Z<T>& lhs, U rhs) { return Z<T>(lhs) *= rhs; }
template <typename T, typename U> Z<T> operator*(U lhs, const Z<T>& rhs) { return Z<T>(lhs) *= rhs; }
template <typename T> Z<T> operator/(const Z<T>& lhs, const Z<T>& rhs) { return Z<T>(lhs) /= rhs; }
template <typename T, typename U> Z<T> operator/(const Z<T>& lhs, U rhs) { return Z<T>(lhs) /= rhs; }
template <typename T, typename U> Z<T> operator/(U lhs, const Z<T>& rhs) { return Z<T>(lhs) /= rhs; }
// using namespace std;;
template<typename T, typename U>
Z<T> power(const Z<T>& a, const U& b) {
assert(b >= 0);
Z<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename T>
bool is_zero(const Z<T>& number) {
return number() == 0;
}
template <typename T>
string to_string(const Z<T>& number) {
return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Z<T>& number) {
return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Z<T>& number) {
typename common_type<typename Z<T>::value_type, long long>::type x;
stream >> x;
number.value = Z<T>::normalize(x);
return stream;
}
} // end of namespace
template<typename T> struct std::hash<math::field::Z<T>> {
std::size_t operator()(math::field::Z<T> const& z) const noexcept {
return std::hash<typename T::value_type>{}(z());
}
};
template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };
class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
typedef std::integral_constant<long long, (long long)1e9 + 7> mod;
using math::field::Z;
const int R = size(board);
const int C = size(board[0]);
using int64 = long long;
const struct {
mutable std::optional<int64> f[100][100];
mutable std::optional<Z<mod>> g[100][100];
} memo;
auto inbound = [&](int r, int c) { return 0 <= r and r < R and 0 <= c and c < C; };
std::function<int64(int, int)> f = [&, memo = std::ref(memo.f)](int i, int j) ->int64 {
if (memo[i][j])
return *memo[i][j];
else
return *(memo[i][j] = [&] {
const int64 score = (board[i][j] == 'E' or board[i][j] == 'S' ? 0 : board[i][j] - '0');
if (i == R - 1 and j == C - 1)
return score;
else
return [&](int64 acc = LONG_MIN / 3) -> int64 {
if (inbound(i, j + 1) and board[i][j + 1] != 'X')
acc = std::max(acc, score + f(i, j + 1));
if (inbound(i + 1, j + 1) and board[i + 1][j + 1] != 'X')
acc = std::max(acc, score + f(i + 1, j + 1));
if (inbound(i + 1, j) and board[i + 1][j] != 'X')
acc = std::max(acc, score + f(i + 1, j));
return acc;
}();
}());
};
std::function<Z<mod>(int, int)> g = [&, memo = std::ref(memo.g)](int i, int j) {
if (memo[i][j])
return *memo[i][j];
else
return *(memo[i][j] = [&]() -> Z<mod> {
const int64 score = board[i][j] == 'E' ? 0 : board[i][j] - '0';
if (i == R - 1 and j == C - 1)
return 1;
else
return [&](Z<mod> acc = 0) {
if (inbound(i, j + 1) and score + f(i, j + 1) == f(i, j))
acc = (acc + g(i, j + 1)) ;
if (inbound(i + 1, j + 1) and score + f(i + 1, j + 1) == f(i, j))
acc = (acc + g(i + 1, j + 1)) ;
if (inbound(i + 1, j) and score + f(i + 1, j) == f(i, j))
acc = (acc + g(i + 1, j)) ;
return acc;
}();
}());
};
const auto solution = vector<int>{f(0, 0) < 0 ? 0 : f(0, 0), int(g(0, 0))};
return solution;
}
};