【题解】矩阵中的路径

比较裸的搜索题，从矩阵的每一个位置开始搜索，看能不能达成一个成功的字符串
这道题给出的矩阵是按一维字符串给的。所以(x,y)应该是x*cols+y

#include<iostream>
#include<cstring>
using namespace std;
class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        for(int i = 0 ; i < rows ; i++)
        {
            for(int j = 0 ; j < cols ; j++)//从矩阵的每一个位置搜索
            {
                memset(visit,0,sizeof(visit));//注意初始化
                if(judge(matrix,rows,cols,str,i,j,0))
                {
                    return true;
                }
            }
        }
        return false;
    }
    bool visit[10000];
    int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
    bool judge(char* matrix, int rows, int cols, char* str, int x, int y,int index)
    {
        visit[x*cols+y]=true;
        if(str[index]!=matrix[x*cols+y]){return false;}
        if(index == strlen(str)-1){return true;}
        for(int i = 0 ; i < 4 ; i++)
        {
            int tx,ty;
            tx = x+dir[i][0];
            ty = y+dir[i][1];
            if(tx>=0&&tx<rows&&ty>=0&&ty<cols&&(!visit[tx*cols+ty]))
            {
                if(judge(matrix,rows,cols,str,tx,ty,index+1)){return true;}
                visit[tx*cols+ty]=false;//注意回溯的时候恢复状态
            }
        }
        return false;
    }

};

int main()
{
    Solution S;
    char G[1000];
    cin >>G;
    int r,c;
    cin >>r >> c;
    char s[100];
    cin >>s;
    cout<<S.hasPath(G,r,c,s);
    return 0;
}
/*
abcesfcsadee
4 4
bcced

ABCESFCSADEE
3 4
ABCB

ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS
5 8
SLHECCEIDEJFGGFIE

ABCEHJIG
SFCSLOPQ
ADEEMNOE
ADIDEJFM
VCEIFGGS
*/