Найти текстовый путь через матрицу символов с помощью рекурсивного алгоритма

Найдите, есть ли в данной матрице путь, который образует предложение «ALL IZZ WELL».

Существует путь от любой ячейки ко всем соседним ячейкам.
Сосед может иметь общее ребро или угол.

Спецификация входных данных:
Первая строка состоит из целого числа t, представляющего количество тестовых наборов.
Первая строка каждого тестового примера состоит из двух целых чисел R и C, представляющих количество строк и количество столбцов в матрице. .

Спецификация выходных данных:
Для каждого теста выведите «YES», если существует путь, который составляет предложение «ALLIZZWELL».
В противном случае выведите «NO».

Чтобы просмотреть примеры тестовых случаев, откройте ссылку.

Мой код:

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
#include <set>
using namespace std;

char matrix[101][101];
bool var;
int r,c;
bool check (string str,int pos, bool visited[101][101],int i, int j);
int main (void)
{
    int t,i,j;
    cin>>t;
    bool ans;
    while (t != 0)
    {
        int r,c,flag=0;
        cin>>r>>c;
        for ( i = 0; i < r; i++ )
        {
            for ( j = 0; j < c; j++ )
            {
                cin>>matrix[i][j];
            } 
        }
        string str = "ALLIZZWELL";
        int pos = 1;
        for ( i = 0; i < r; i++ )
        {
            for ( j = 0; j < c; j++ )
            {
                bool visited[101][101];
                for ( i = 0; i < 101; i++ )
                    for ( j = 0; j < 101; j++ )
                        visited[i][j] = false;
                visited[i][j] = true;
                if (matrix[i][j] == 'A') // for all possible starting positions
                ans = check(str,pos,visited,i,j); 
                if (ans == true)
                {
                    cout<<"YES\n";
                    flag = 1;
                    break;
                }
                if (flag == 1)
                    break;
            }
        }
        if (flag == 0)
            cout<<"NO\n";
        t--;
    }
    return 0;
}

bool check (string str,int pos, bool visited[101][101],int i, int j) // checking for all possible test cases
{
    bool result = false;
    if (pos == str.length() + 1)
        return true;
    if (i+1 < r && visited[i+1][j] != true && matrix[i+1][j] == str[pos])
    {
        visited[i+1][j] = true;
        result = result || check(str,pos+1,visited,i+1,j);
        if (result == false)
            visited[i+1][j] = false;
    }
    else if (i-1 >= 0 && visited[i-1][j] != true && matrix[i-1][j] == str[pos])
    {
        visited[i-1][j] = true;
        result = result || check(str,pos+1,visited,i-1,j);
        if (result == false)
            visited[i-1][j] = true;
    }
    else if (j+1 < c && visited[i][j+1] != true && matrix[i][j+1] == str[pos])
    {
        visited[i][j+1] = true;
        result = result || check(str,pos+1,visited,i,j+1);
        if (result == false)
            visited[i][j+1] = true;
    }
    else if (j-1 >= 0 && visited[i][j-1] != true && matrix[i][j-1] == str[pos])
    {
        visited[i][j-1] = true;
        result = result || check(str,pos+1,visited,i,j-1);
        if (result == false)
            visited[i][j-1] = true;
    }
    else if (i+1 < r && j+1 < c && visited[i+1][j+1] != true && matrix[i+1][j+1] == str[pos])
    {
        visited[i+1][j+1] = true;
        result = result || check(str,pos+1,visited,i+1,j+1);
        if (result == false)
            visited[i+1][j+1] = true;
    }
    else if (i+1 < r && j-1 >= 0 && visited[i+1][j-1] != true && matrix[i+1][j-1] == str[pos])
    {
        visited[i+1][j-1] = true;
        result = result || check(str,pos+1,visited,i+1,j-1);
        if (result == false)
            visited[i+1][j-1] = true;
    }
    else if (i-1 >= 0 && j+1 < c && visited[i-1][j+1] != true && matrix[i-1][j+1] == str[pos])
    {
        visited[i-1][j+1] = true;
        result = result || check(str,pos+1,visited,i-1,j+1);
        if (result == false)
            visited[i-1][j+1] = true;
    }
    else if (i-1 >= 0 && j-1 >= 0 && visited[i-1][j-1]!= true && matrix[i-1][j-1] == str[pos])
    {
        visited[i-1][j-1] = true;
        result = result || check(str,pos+1,visited,i-1,j-1);
        if (result == false)
            visited[i-1][j-1] = true;
    }
    return false;
}

Код говорит сам за себя: я пробую все возможные случаи.

Я получаю WA в третьем тестовом примере, т.е.

2 9
A.L.Z.E..
.L.I.W.L.

Я пробовал отлаживать, но не смог сузить свою проблему.