Skip to content

Instantly share code, notes, and snippets.

@ernestognw
Created November 30, 2019 23:02
Show Gist options
  • Save ernestognw/6942a6b4834fb5ad903194f9c5f25b75 to your computer and use it in GitHub Desktop.
Save ernestognw/6942a6b4834fb5ad903194f9c5f25b75 to your computer and use it in GitHub Desktop.
// boogle
// Ernesto García A00820783
// Created at Mon Nov 18 01:04:02 CST 2019
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int BFS(int i, int j, string word, int positionInWord, vector<vector<bool> > visited, vector <vector<char> > &grid){
if(i < 0 || j < 0 || i >= 4 || j >= 4 || positionInWord >= word.length()) return 0;
if(visited[i][j] || word[positionInWord] != grid[i][j]) return 0;
visited[i][j] = true;
int nextPosition = positionInWord + 1;
int right = BFS(i + 1, j, word, nextPosition, visited, grid);
int left = BFS(i - 1, j, word, nextPosition, visited, grid);
int up = BFS(i, j - 1, word, nextPosition, visited, grid);
int down = BFS(i, j + 1, word, nextPosition, visited, grid);
int rightUp = BFS(i + 1, j - 1, word, nextPosition, visited, grid);
int leftUp = BFS(i - 1, j - 1, word, nextPosition, visited, grid);
int rightDown = BFS(i + 1, j + 1, word, nextPosition, visited, grid);
int leftDown = BFS(i - 1, j + 1, word, nextPosition, visited, grid);
int maxLength = 0;
maxLength = max(maxLength, right);
maxLength = max(maxLength, left);
maxLength = max(maxLength, up);
maxLength = max(maxLength, down);
maxLength = max(maxLength, rightUp);
maxLength = max(maxLength, leftUp);
maxLength = max(maxLength, rightDown);
maxLength = max(maxLength, leftDown);
return 1 + maxLength;
}
int getPoints(string word, vector <vector<char> > &grid){
int maxLength = 0;
vector<int> pointsMap;
pointsMap.push_back(0);
pointsMap.push_back(0);
pointsMap.push_back(0);
pointsMap.push_back(1);
pointsMap.push_back(1);
pointsMap.push_back(2);
pointsMap.push_back(3);
pointsMap.push_back(5);
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(grid[i][j] == word[0]) {
vector<vector<bool> > visited(4, vector<bool> (4, false));
int length = BFS(i, j, word, 0, visited, grid);
if(length == word.length()) maxLength = length;
}
}
}
return maxLength > 7 ? 11 : pointsMap[maxLength];
}
void readGrid(vector <vector<char> > &grid){
for(int i = 0; i < 4; i++){
string line;
vector <char> gridLine;
getline(cin, line);
for(int j = 0; j < 4; j++){
gridLine.push_back(line[j]);
}
grid.push_back(gridLine);
}
}
int main() {
// Declare variables
vector <int> gamePoints;
int n;
cin >> n;
cin.ignore();
while(n--){
int points = 0;
vector <vector<char> > grid;
readGrid(grid);
int dictLength;
cin >> dictLength;
cin.ignore();
for(int i = 0; i < dictLength; i++){
string word;
cin >> word;
cin.ignore();
points += getPoints(word, grid);
}
gamePoints.push_back(points);
}
for(int i = 0; i < gamePoints.size(); i++){
cout << "Game " << i + 1 << ": " << gamePoints[i] << endl;
}
// End program
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment