[UVa] 10010 - Where's Waldorf?

題目

Link: UVa 10010 - Where's Waldorf?

Code

C++

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

void find(const std::vector<std::string>& map, const std::string& word, int& row, int& col);

int main()
{
  int cases;
  int rows, cols;
  int row, col;
  std::string buffer;
  std::vector<std::string> map;
  std::vector<std::string> word_list;
  int word_list_len;

  int i;

  // free synchronization
  std::ios::sync_with_stdio(false);

  std::cin >> cases;

  while (cases--)
  {
    std::cin >> rows >> cols;
    map.clear();
    for (i = 0; i < rows; ++i)
    {
      std::cin >> buffer;
      // to lower case
      std::transform(buffer.begin(), buffer.end(), buffer.begin(), ::tolower);
      map.push_back(buffer);
    }

    std::cin >> word_list_len;
    word_list.clear();
    for (i = 0; i < word_list_len; ++i)
    {
      std::cin >> buffer;
      std::transform(buffer.begin(), buffer.end(), buffer.begin(), ::tolower);
      word_list.push_back(buffer);
    }

    for (const auto& word : word_list)
    {
      find(map, word, row, col);
      std::cout << row << " " << col << std::endl;
    }
    if (cases) std::cout << std::endl;
  }

  return 0;
}

void find(const std::vector<std::string>& map, const std::string& word, int& row, int& col)
{
  static const int DIRECTIONS[][2] = {{-1, -1}, {-1, 0}, {-1, 1},
                               {0, -1}, /*{0, 0},*/ {0, 1}, // This's an accident.
                               {1, -1}, {1, 0}, {1, 1}};
  int i, j, row_dest, col_dest, r, c;
  int m = static_cast<int>(map.size()), n;

  for (i = 0; i < m; ++i)
    for (j = 0; j < (n = static_cast<int>(map[i].length())); ++j)
      for (const auto* direction : DIRECTIONS)
      {
        // boundary check
        row_dest = i + direction[0] * static_cast<int>(word.length() - 1);
        if (row_dest < 0 or row_dest >= m) continue;
        col_dest = j + direction[1] * static_cast<int>(word.length() - 1);
        if (col_dest < 0 or col_dest >= n) continue;

        // check each character
        r = i, c = j;
        for (auto ch : word)
        {
          if (map[r][c] != ch) break;
          r += direction[0];
          c += direction[1];
        }

        // complete checking
        if (r - direction[0] == row_dest and c - direction[1] == col_dest)
        {
          row = i + 1, col = j + 1;
          return;
        }
      }
}

Show Comments