wordGame.cpp

// Author:	黃志仁
// Stu ID:	B10530027
// Class:	四不分一甲
// Problem:	Word Game

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
char grid[4][4];
bool used[4][4] = {0};

bool recur(string str, int x, int y, int p) {//recursion function
	if (str[p] != grid[x][y])
		return false;	//not valid
	else
		used[x][y]=true;//set it as used

	if(p==str.length()-1 && str[p] == grid[x][y]) 
		return true;	//end of one input && still valid

	if (x + 1 < 4 && y + 1 < 4  && !used[x + 1][y + 1] && recur(str, x + 1, y + 1, p + 1))
		return true;
	else if (x + 1 < 4 && !used[x + 1][y] && recur(str, x + 1, y, p + 1))
		return true;
	else if (y + 1 < 4 && !used[x][y + 1] && recur(str, x, y + 1, p + 1))
		return true;
	else if (x - 1 >= 0 && y - 1 >= 0 && !used[x - 1][y - 1] && recur(str, x - 1, y - 1, p + 1))
		return true;
	else if (x - 1 >= 0 && !used[x - 1][y] &&recur(str, x - 1, y, p + 1))
		return true;
	else if (y - 1 >= 0 && !used[x][y - 1] && recur(str, x, y - 1, p + 1))
		return true;
	else if (!used[x - 1][y + 1] && recur(str, x - 1, y + 1, p + 1))
		return true;
	else if (x + 1 < 4 && y - 1 >= 0 && !used[x + 1][y - 1] && recur(str, x + 1, y - 1, p + 1))
		return true;
	else
		return false; 	//else = not valid
}
void clear(){//set all used array to false
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			used[i][j]=false;
}	
int main() {
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			cin >> grid[i][j];	//input grid
	ifstream fin("words.txt");	
	string str;
	while (fin >> str) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				//find first char'position of str
				if (grid[i][j] == str[0]) {
					if (recur(str, i, j, 0)) //if recur result is true
						cout << str << endl;
					clear();
				}
			}
		}
	}
}