algorithm - 使用递归算法通过字符矩阵查找文本路径

Question

我正在尝试解决这个问题:http://www.spoj.com/problems/ALLIZWEL/

Find whether there is a path in the given matrix which makes the sentence “ALL IZZ WELL”.

There is a path from any cell to all its neighbouring cells.
A neighbour may share an edge or a corner.

Input Specification:
The first line consists of an integer t representing the number of test cases.
The first line of each test case consists of two integers R and C representing the number of rows and number of columns in the matrix.

Output Specification:
For each test case print “YES” if there is a path which makes the sentence “ALLIZZWELL”.
Else print “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.

我试过调试，但无法缩小我的问题范围。

Answer 1

主要问题是:

1. 在循环清除访问(以及外部循环)中使用 i 和 j
2. 在check中使用r和c作为全局变量，在main中写成局部变量
3. 总是从检查中返回 false(而不是结果)
4. 只尝试检查第一个选择(将“else if”变成“if”)
5. 不清除ans中的值
6. 只跳出内循环，不跳出第 i 和 j 循环
7. 当 pos 到达 str.length()+1 而不是 str.length() 时终止搜索

在像这样的递归函数中放置一些打印语句通常会有所帮助，在一个简单的例子中尝试它们，看看调用顺序是否符合您的期望。