Looking for feedback especially regarding design/structure/naming but also anything else that can be improved upon.
Task: Given a (hardcoded) matrix, find out if a given string can be found without visiting a cell twice. Movement is restricted to horizontal/vertical and only adjacent cells can be visited. Print "True" if the input string can be found "False" otherwise.
Matrix:
ABCE
SFCS
ADEE
Example:
Input: CSE
Result: True. (Start from the C in the 2nd row, go right, go up)
Source code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <set>
using std::get;
using std::make_tuple;
const std::vector<std::vector<char>> matrix =
{
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'},
};
const std::vector<std::tuple<int, int>> directions =
{
make_tuple(-1, 0),
make_tuple(0, 1),
make_tuple(1, 0),
make_tuple(0, -1),
};
std::set<std::tuple<int, int>> used;
std::string chars;
bool find_next_match(size_t index, std::tuple<int, int> cur_pos)
{
if (index == chars.size() - 1) return true;
++index;
used.insert(cur_pos);
for (const auto &dir : directions)
{
auto new_pos = make_tuple(get<0>(cur_pos) + get<0>(dir), get<1>(cur_pos) + get<1>(dir));
if (get<0>(new_pos) < 0 || get<0>(new_pos) > 2) continue;
if (get<1>(new_pos) < 0 || get<1>(new_pos) > 3) continue;
if (used.count(new_pos)) continue;
if (matrix[get<0>(new_pos)][get<1>(new_pos)] != chars[index]) continue;
if (find_next_match(index, new_pos)) return true;
}
used.erase(cur_pos);
return false;
}
int main (int argc, char **argv)
{
std::ifstream infile(argv[1], std::ios::in | std::ifstream::binary);
std::string line;
while (getline(infile, line))
{
chars.clear();
chars = line;
bool found = false;
for (int m = 0; m < 3; ++m)
{
for (int n = 0; n < 4; ++n)
{
if (matrix[m][n] == chars[0])
{
used.clear();
if (find_next_match(0, make_tuple(m, n)))
{
found = true;
break;
}
}
if (found) break;
}
}
if (found) std::cout << "True\n";
else std::cout << "False\n";
}
}
Edit 1:
I changed the find_next_match function to operate on the string directly instead of passing an addiontal argument to keep the amount of arguments under 3 (as per recommendation in Robert C. Martins Clean Code)
Revision 2 based on advice by @vnp
Edit 2:
Revision 3 based on advice by @miscco