上次上课听的有点懵,今天重点理解字符串哈希和深度优先搜索(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;
}