Maze
今天看到这道搜索题，发现很久没写bfs都不熟练了。。。
由于要求字母不能重复用，因此还是和普通BFS DFS一样，visit数组来判断是否访问，只在匹配到了字符串才置对应位为1，
BFS里面由于增加了匹配，因此如果未匹配应该是取下一个queue的内容，continue到下一轮循环，之前把pop写到后面去了，导致死循环，front() 和pop()以后要紧跟，因为后面可能加些访问
之类的东西，例如这里加了一个如果当前不match就return，导致只peek却没有pop。
dfs也是一样，忘记了不match直接return，以为不加也是一样，其实如果不加的话，可能当前不匹配但是后面扩展又匹配导致出错甚至死循环，由于dfs是递归算法，因此只能设置标志位
来判断是否match了，因此效率应该是不如bfs的。
#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
int n,m;
char str[100+1];
char mat[22][22];
bool visit[22][22];
int dfs_stri;
bool dfs_found;
bool search_bfs()
{
int stri;
pair<int, int> p;
for(int i=0;i<=n-1;i++)
{
for(int j=0;j<=m-1;j++)
{
for(int i=0;i<=n-1;i++)
memset(visit[i],0,sizeof(bool)*m);
stri=0;
if(mat[i][j]!=str[stri])
continue;
queue<pair<int, int> > q;
q.push({i,j});
while(!q.empty())
{
p=q.front();
q.pop();
if(mat[p.first][p.second]==str[stri])
stri++,visit[p.first][p.second]=1;
else
continue;
if(!str[stri])
{
//cout<<i<<" "<<j<<" "<<p.first<<" "<<p.second<<endl;
return true;
}
if(p.first-1>=0 && visit[p.first-1][p.second]==false && mat[p.first-1][p.second]==str[stri])
q.push({p.first-1,p.second});
if(p.first+1<=n-1 && visit[p.first+1][p.second]==false && mat[p.first+1][p.second]==str[stri])
q.push({p.first+1,p.second});
if(p.second-1>=0 && visit[p.first][p.second-1]==false && mat[p.first][p.second-1]==str[stri])
q.push({p.first,p.second-1});
if(p.second+1<=m-1 && visit[p.first][p.second+1]==false && mat[p.first][p.second+1]==str[stri])
q.push({p.first,p.second+1});
}
}
}
return false;
}
void dfs(pair<int, int> p)
{
if(mat[p.first][p.second]==str[dfs_stri])
dfs_stri++,visit[p.first][p.second]=1;
else
return ;
if(!str[dfs_stri])
{
dfs_found=true;
return ;
}
if(p.first-1>=0 && !visit[p.first-1][p.second] && mat[p.first-1][p.second]==str[dfs_stri])
dfs({p.first-1,p.second});
if(p.first+1<= n-1 && !visit[p.first+1][p.second] && mat[p.first+1][p.second]==str[dfs_stri])
dfs({p.first+1,p.second});
if(p.second-1>=0 && !visit[p.first][p.second-1] && mat[p.first][p.second-1]==str[dfs_stri])
dfs({p.first,p.second-1});
if(p.second+1<= m-1 && !visit[p.first][p.second+1] && mat[p.first][p.second+1]==str[dfs_stri])
dfs({p.first,p.second+1});
}
bool search_dfs()
{
for(int i=0;i<=m-1;i++)
{
for(int j=0;j<=n-1;j++)
{
for(int k=0;k<=n-1;k++)
memset(visit[k],0,sizeof(visit[k]));
dfs_stri=0;
dfs_found=false;
dfs(make_pair(i,j));
if(dfs_found)
{
cout<<i<<" "<<j<<endl;
return true;
}
}
}
return false;
}
/*
bool search()
{
int si, sj,stri;
for(int i=0;i<=n-1;i++)
{
for(int j=0;j<=m-1;j++)
{
si=i,sj=j;
stri=0;
while(str[stri])
{
if(si-1>=0 && mat[si-1][sj]==str[stri])//up
stri++,si--;
else if(si+1<=n-1 && mat[si+1][sj]==str[stri])//down
stri++, si++;
else if(sj-1>=0 && mat[si][sj-1]==str[stri])//left
stri++,sj--;
else if(sj+1<=m-1 && mat[si][sj+1]==str[stri])//right
stri++,sj++;
else
break;
}
//if(str[stri])
// return 0;
if(!str[stri])
{
cout<<i<<" "<<j<<endl<<si<<" "<<sj<<endl;
return true;
}
}
}
return false;
}*/
int main()
{
freopen("maze.in","r",stdin);
scanf("%d%d ",&n,&m);
//gets(str);
//cout<<str<<endl;
for(int i=0;i<n;i++)
scanf("%s ",mat[i]),cout<<mat[i]<<endl;
/*
if(search_bfs())
puts("YES");
else
puts("NO");
*/
while(gets(str))
{
cout<<str<<endl;
if(search_dfs())
puts("YES");
else
puts("NO");
}
return 0;
}
今天在外面看到vogue这个词，查了知道是时尚，时髦的意思，在自行车上很多