aoj-2620.cpp

#include <cstdio>
#include <cstring>

#include "../include/graph/dijkstra.cpp"
#include "../include/graph/weighted_graph.cpp"
#include "../include/types/serial.cpp"

#define REP(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int ri[512][512], dw[512][512];
char str[1024];

int main() {
  int H, W, N, sx, sy, gx, gy;
  scanf("%d%d%d", &W, &H, &N);
  scanf("%d%d%d%d", &sx, &sy, &gx, &gy);
  REP(i, N) {
    int x, y, t;
    scanf("%d%d%d%s", &x, &y, &t, str);
    REP(j, t) {
      int len = strlen(str);
      for (int k = 0; k < len; ++k) {
        char c = str[k];
        if (c == 'U' && y > 0) {
          ++ri[y][x];
          --y;
        }
        else if (c == 'D' && y < H - 1) {
          ++y;
          ++ri[y][x];
        }
        else if (c == 'L' && x > 0) {
          ++dw[y][x];
          --x;
        }
        else if (c == 'R' && x < W - 1) {
          ++x;
          ++dw[y][x];
        }
      }
    }
  }
  WeightedGraph<int> g((H + 1) * (W + 1));
  Serial::reset();
  vector<vector<Serial>> node;
  REP(i, H + 1) node.emplace_back(W + 1);
  assert(Serial::size() == (H + 1) * (W + 1));
  REP(i, H + 1) REP(j, W) {
    add_edge(g, node[i][j], node[i][j + 1], ri[i][j]);
    add_edge(g, node[i][j + 1], node[i][j], ri[i][j]);
  }
  REP(i, H) REP(j, W + 1) {
    add_edge(g, node[i][j], node[i + 1][j], dw[i][j]);
    add_edge(g, node[i + 1][j], node[i][j], dw[i][j]);
  }
  vector<int> d = dijkstra(g, node[sy][sx]);
  printf("%d\n", d[node[gy][gx]]);
  return 0;
}