A - Union of Grid Paths
Source: atcoder
Difficulty: 400

Problem Statement
There is an
H\times W
grid of cells. Let
(h,w)
denote the cell at the
h
-th row from the top and the
w
-th column from the left. Furthermore, you are given a string
S = S_1\cdots S_{H+W-2}
of length
H+W-2
consisting of
D
,
R
, and
?
.
Initially, all cells are painted white. You may perform the following operation, which consists of three steps, any number of times:
Choose a string
X = X_1\cdots X_{H+W-2}
of length
H+W-2
satisfying all of the following.
X
consists of exactly
H-1
D
s and
W-1
R
s.
For each
1 \le i \le H+W-2
, if
S_i
is
D
then
X_i
must also be
D
.
For each
1 \le i \le H+W-2
, if
S_i
is
R
then
X_i
must also be
R
.
Stand on cell
(1,1)
. Then for
i=1,2,\ldots
in order, move one cell in the direction indicated by
X_i
: if
X_i
is
D
, move down one cell; if
X_i
is
R
, move right one cell. It can be shown that if
X
satisfies the conditions in step 1, the destination cell always exists within the grid.
For every cell you visited in step 2 (including the starting and ending cells), if the cell is currently white, paint it black.
Find the maximum possible number of cells that can be painted black in total.
There are
T
test cases; solve each one.
Constraints
1\le T\le 2\times 10^5
2\le H,W\le 2\times 10^5
T,H,W
are integers.
S
is a string of length
H+W-2
consisting of
D
,
R
, and
?
.
The number of
D
s in
S
is at most
H-1
.
The number of
R
s in
S
is at most
W-1
.
The sum of
H+W
over all test cases is at most
4\times 10^5
.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T
Each case is given in the following format:
H
W
S
Output
Print
T
lines. The
i
-th line should contain the maximum number of cells that can be painted black for the
i
-th test case.
Sample Input 1
4
4 5
D?DRR?R
4 5
DDRRDRR
4 5
???????
2 2
DR
Sample Output 1
12
8
20
3
For the first test case, by choosing
X
as
DRDRRDR
in the first operation and
DDDRRRR
in the second operation, you can paint
12
cells black.

C++ solution:
#include <iostream>
#include <algorithm>
using namespace std;

void solve() {
	int h, w;
	cin >> h >> w;
	string s;
	cin >> s;
	long long not_reachable = 0;
	pair<int, int> pos = make_pair(1, 1);
	int moved_right = 0;
	int to_move_right = count(s.begin(), s.end(), 'R');
	for (char dir : s) {
		to_move_right -= (dir == 'R');
		if (dir == 'D' || moved_right + to_move_right == w - 1) {
			not_reachable += w - pos.second;
			++pos.first;
		}
		else {
			++pos.second;
			++moved_right;
		}
	}
	pos = make_pair(1, 1);
	int moved_down = 0;
	int to_move_down = count(s.begin(), s.end(), 'D');
	for (char dir : s) {
		to_move_down -= (dir == 'D');
		if (dir == 'R' || moved_down + to_move_down == h - 1) {
			not_reachable += h - pos.first;
			++pos.second;
		}
		else {
			++pos.first;
			++moved_down;
		}
	}
	cout << (long long)h * w - not_reachable << '\n';
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		solve();
	}
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var scanner *bufio.Scanner
var writer *bufio.Writer

func init() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024) 
	scanner.Split(bufio.ScanWords)
	writer = bufio.NewWriter(os.Stdout) 
}

func main() {
	defer writer.Flush() 
	t := readInt() 
	for i := 0; i < t; i++ {
		fmt.Fprintln(writer, solve()) 
	}
}

func solve() int64 {
	h := readInt() 
	w := readInt() 
	s := readString() 
	n := len(s) 

	dTotal := h - 1 
	rTotal := w - 1 

	dsPref := make([]int, n+1)
	rsPref := make([]int, n+1)

	for i := 0; i < n; i++ {
		dsPref[i+1] = dsPref[i]
		rsPref[i+1] = rsPref[i]
		if s[i] == 'D' {
			dsPref[i+1]++
		} else if s[i] == 'R' {
			rsPref[i+1]++
		}
	}

	ds := dsPref[n]
	rs := rsPref[n]

	var totalBlackCells int64 = 0

	for k := 0; k <= n; k++ {
		dkPrefix := dsPref[k]
		rkPrefix := rsPref[k]

		minDk := max(dkPrefix, k - rTotal + rs - rkPrefix)
		maxDk := min(k - rkPrefix, dTotal - ds + dkPrefix)

        lowerBound := max(minDk, 0, k - w + 1)
        upperBound := min(maxDk, h - 1, k)

        var countK int64 = 0
		if upperBound >= lowerBound {
			countK = int64(upperBound - lowerBound + 1)
		}

		totalBlackCells += countK
	}

	return totalBlackCells
}

func max(a ...int) int {
    if len(a) == 0 {
       panic("max called with no arguments") 
    }
	res := a[0]
	for _, v := range a[1:] {
		if v > res {
			res = v
		}
	}
	return res
}

func min(a ...int) int {
     if len(a) == 0 {
         panic("min called with no arguments")
    }
	res := a[0]
	for _, v := range a[1:] {
		if v < res {
			res = v
		}
	}
	return res
}

func readString() string {
	if !scanner.Scan() {
         panic(fmt.Sprintf("Failed to scan token: %v", scanner.Err()))
    }
	return scanner.Text()
}

func readInt() int {
	val, err := strconv.Atoi(readString())
	if err != nil {
		panic(fmt.Sprintf("Failed to parse integer: %v", err))
	}
	return val
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;

public class Main {
  private static void execute(ContestReader reader, ContestWriter out) {
    int q = reader.nextInt();
    for (int i = 0; i < q; i++) {
      long h = reader.nextLong();
      long w = reader.nextLong();
      char[] cs = reader.nextCharArray();
      long countD = 0;
      long countR = 0;
      for (char c : cs) {
        if (c == 'D') {
          countD++;
        } else if (c == 'R') {
          countR++;
        }
      }

      long restD = h - 1 - countD;
      long restR = w - 1 - countR;
      long pDRF = 0;
      long pDRS = 0;
      long pRDF = 0;
      long pRDS = 0;
      long answer = 0;
      long numFork = 1;
      for (char c : cs) {
        answer += numFork;
        if (c == '?') {
          if (pDRF < restD) {
            pDRF++;
          } else {
            pDRS++;
          }

          if (pRDS < restR) {
            pRDS++;
          } else {
            pRDF++;
          }
          numFork = pDRF - pRDF + 1;
        }
      }
      answer += numFork;
      out.println(answer);
    }
  }

  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    ContestWriter out = new ContestWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestWriter extends PrintWriter {
  ContestWriter(PrintStream printStream) {
    super(printStream);
  }

  public void printYN(boolean b) {
    println(b ? "Yes" : "No");
  }

  public void printYNList(List<Boolean> bList) {
    for (boolean b : bList) {
      printYN(b);
    }
  }

  public void printList(List<? extends Object> list) {
    for (Object object : list) {
      println(object);
    }
  }

  public void printListOneLine(List<? extends Object> list) {
    List<String> stringList = new ArrayList<>();
    for (Object object : list) {
      stringList.add(object.toString());
    }
    println(String.join(" ", stringList));
  }
}

class ContestReader {
  private static final int BUFFER_SIZE = 1024;
  
  private final InputStream stream;
  private final byte[] buffer;
  private int pointer;
  private int bufferLength;
  
  ContestReader(InputStream stream) {
    this.stream = stream;
    this.buffer = new byte[BUFFER_SIZE];
    this.pointer = 0;
    this.bufferLength = 0;
  }
  
  private boolean hasNextByte() {
    if (pointer < bufferLength) {
      return true;
    }
    
    pointer = 0;
    try {
      bufferLength = stream.read(buffer);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    return bufferLength > 0;
  }
  
  private int readByte() {
    if (hasNextByte()) {
      return buffer[pointer++];
    } else {
      return -1;
    }
  }
  
  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }
  
  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
      pointer++;
    }
    return hasNextByte();
  }
  
  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b)) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public String nextLine() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b) && b != 0x20) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public char nextChar() {
    return next().charAt(0);
  }
  
  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    int n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    long n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public String[] nextLine(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLine();
    }
    return array;
  }
  
  public char[] nextChar(int n) {
    char[] array = new char[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextChar();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public String[][] next(int n, int m) {
    String[][] matrix = new String[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = next();
      }
    }
    return matrix;
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public char[][] nextChar(int n, int m) {
    char[][] matrix = new char[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextChar();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}

class Pair<T extends Comparable<T>, U extends Comparable<U>> implements Comparable<Pair<T, U>> {
  T first;
  U second;

  Pair(T first, U second) {
    this.first = first;
    this.second = second;
  }

  public int compareTo(Pair<T, U> p) {
    int tResult = first.compareTo(p.first);
    if (tResult != 0) {
      return tResult;
    }
    return second.compareTo(p.second);
  }
}

class MyAssert {
  public static void myAssert(boolean flag, String message) {
    if (!flag) {
      throw new RuntimeException(message);
    }
  }
 
  public static void myAssert(boolean flag) {
    myAssert(flag, "");
  }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = next();
  while(q--)print(solve());
}

function solve(){
  var [h,w] = nexts(2);
  var s = nextstr();
  var d = 0, r = 0;
  for(var i = 0; i < s.length; i++){
    switch(s[i]){
      case "D": d++; break;
      case "R": r++; break;
    }
  }
  var hu = Array(w);
  hu[0] = 0;
  for(var i = 0, y = 0, x = 0, rr = 0; i < s.length; i++){
    var t = s[i];
    if(t === "?"){
      if(r+rr+1 < w){
        rr++; t = "R";
      }else{
        t = "D";
      }
    }
    switch(t){
      case "D": y++; break;
      case "R": x++; hu[x] = y; break;
    }
  }
  var hd = Array(w);
  for(var i = 0, y = 0, x = 0, rr = 0; i < s.length; i++){
    var t = s[i];
    if(t === "?"){
      if(d+rr+1 < h){
        rr++; t = "D";
      }else{
        t = "R";
      }
    }
    switch(t){
      case "D": y++; break;
      case "R": hd[x] = y; x++; break;
    }
  }
  hd[w-1] = h-1;
  var ans = 0;
  for(var i = 0; i < w; i++){
    ans += hd[i] - hu[i] + 1;
  }
  return ans;
}

Python solution:
import sys

# from atcoder.fenwicktree import FenwickTree
# from atcoder.segtree import SegTree
# from atcoder.lazysegtree import LazySegTree
# from atcoder.string import suffix_array,lcp_array,z_algorithm
# from atcoder.math import inv_mod,crt,floor_sum
# from atcoder.convolution import convolution,convolution_int
# from atcoder.modint import ModContext,Modint
# from atcoder.dsu import DSU
# from atcoder.maxflow import MFGraph
# from atcoder.mincostflow import MCFGraph
# from atcoder.scc import SCCGraph
# from atcoder.twosat import TwoSAT


def debug(*args, sep=" ", end="\n") -> None:
    print(*args, sep=sep, end=end, file=sys.stderr)


def main():
    global inf, MOD
    input = sys.stdin.read().split()
    ptr = 0
    inf = float("inf")
    MOD = 998244353

    T = int(input[ptr]); ptr += 1
    for _ in range(T):
        H, W = map(int, input[ptr:ptr + 2]); ptr += 2
        S = input[ptr]; ptr += 1
        ans = 1
        D = S.count('D')
        R = S.count('R')
        H + W - 2 - D - R
        d = H - 1 - D
        r = W - 1 - R
        m = 1
        for s in S:
            if s == '?':
                if d > 0 and r > 0:
                    d -= 1
                    r -= 1
                    m += 1
                elif d > 0 and r == 0:
                    d -= 1
                elif d == 0 and r > 0:
                    r -= 1
                else:
                    m -= 1
            ans += m
        print(ans)


if __name__ == "__main__":
    main()

Ruby solution:
gets.to_i.times do
  h, w = gets.split.map &:to_i
  s = gets.chomp
  d, r = s.count('D'), s.count('R')
  q = 0
  ans = 1
  b = 1
  s.each_char do |i|
    if i == '?' then
      q += 1
      if d + q <= h - 1 && r + q <= w - 1 then
        b += 1
      elsif d + q > h - 1 && r + q > w - 1 then
        b -= 1
      end
    end
    ans += b
  end
  puts ans
end