上次上课听的有点懵，今天重点理解字符串哈希和深度优先搜索（DFS），暂时还没理解广度优先搜索（BFS），并总结自己对字符串哈希和DFS的理解；

1.字符串哈希：就是将对应的字符串转换为ASCLL码值并储存再数组中，例如字符串ABC123；

A的ASCLL码值为65；同理BC，分别为66，67；123分别为49，50，51；如果将字符串哈希转化为10进制的数组中，则对应的数组为:a[0]=0; a[1]=a[0]*10+65; a[2]=a[1]*10+66; a[3]=a[2]*10+67; a[4]=a[3]*10+49; a[5]=a[4]*10+50; a[6]=a[5]*10+51;

然后我们可以根据题目需要来提取区域字符串；

例题：记不清了，大概是这样的

输入n，m；后输入以n为长度的字符串；

然后输入m组a,b,c,d；a,b为子字符串的左右端点，c，d为另一字符串左右端点；判断两字符串是否相等；

输入：8 3

aabbaabb

1 2 3 4

2 4 6 8

3 4 5 7

输出：

NO

YES

NO

代码：

#include<iostream>
#include<algorithm>
using namespace std;

typedef unsigned long long ull;                   //防止数据过大给炸了
const int maxn = 1e5 + 10;
ull h[maxn],e[maxn];
int p = 13331;                                        //鲁氏经验告诉我最好是13331进制或131进制
char s[maxn];

ull find(int l, int r)
{
    return h[r] - h[l - 1] * e[r - l + 1];     //提取子字符串，注：* e[r - l + 1]是为了精准提取，如提取字
}                                                        //符串ABC中的B，应该是h[r]=A*p^1+B*p^0；h[l]=A*p^1；所

int main()                                          //以子字符串B应该为h[r]-h[l]*p;
{
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m >> s + 1;
    e[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * p + s[i];
        e[i] = e[i - 1] * p;
    }
    while (m--)
    {
        int f1, l1, f2, l2;
        cin >> f1 >> l1 >> f2 >> l2;
        if (find(f1, l1) == find(f2, l2))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

深度优先搜索：

题目描述 
给你一个n*m的迷宫，这个迷宫中有以下几个标识：

s代表起点

t代表终点

x代表障碍物

.代表空地

现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。

输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点
输出描述:
对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO
示例1
输入
1
3 5
s...x
x...x
...tx
输出
YES

#include<bits/stdc++.h>
using namespace std;
const int maxn=550;
char t[maxn][maxn];
int flag[maxn][maxn]={0};
int change[2][4]={0,1,0,-1,1,0,-1,0};
int ok=0;
int n,m;
void dfs(int x,int y)
{
    if(t[x][y]=='t')   //若该字符为终止字符
    {
        ok=1;
    }
    int nx,ny;
    for(int i=0;i<4;i++)
    {
        nx=x+change[0][i];
        ny=y+change[1][i];
        if(nx>=0&&nx<n&&ny>=0&&ny<m&&t[nx][ny]!='x'&&flag[nx][ny]==0)
        {
            flag[nx][ny]=1;
            dfs(nx,ny);
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ok=0;
        memset(flag,0,sizeof flag);
        cin>>n>>m;
        int x,y;   //由于记录开始坐标
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>t[i][j];
                if(t[i][j]=='s')
                {
                    x=i;
                    y=j;
                }
            }
        }
        dfs(x,y);
        if(ok)
            cout<<"YES"<<"\n";
        else
            cout<<"NO"<<"\n";
    }
    return 0;
}