Created
November 30, 2019 23:02
-
-
Save ernestognw/6942a6b4834fb5ad903194f9c5f25b75 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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