题目在这里:http://acm.hdu.edu.cn/showproblem.php?pid=1175
大家都很熟悉的连连看,原理基本就是这个,典型的搜索.这里用的是广搜.深搜的在下面
与普通的搜索比不同的是要求转折的线不能转折超过两次,就是在结构体中多开一个step(储存转折的次数)和一个dir(记录此刻的方向)
方向初始为-1,当行走一步后的方向与走之前不同的时候,step就应该加一,
然后还要注意的是为了保证得到的是所有的路线中转折次数最小的,这里的visit数组要用来保存每个点的最小转折次数,
所以初始化应该为很大
具体的看code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<climits>
using namespace std;
int map[][],visit[][];
struct point {
int x,y;
int step,dir;//记录转折次数与方向
} ;
int dx[]={,,,-};
int dy[]={,-,,};
int n,m,ex,ey;
int bfs(int sx,int sy)
{
int i;
queue<point>Q;
point next,now;
now.x=sx;now.y=sy;
now.step=;
now.dir=-;
Q.push(now);
while (!Q.empty())
{
now=Q.front();
Q.pop();
if (now.x==ex&&now.y==ey)
return ;
for (i=;i<;i++)
{
next.x=now.x+dx[i];
next.y=now.y+dy[i];
next.step=now.step;
next.dir=i;
if (next.dir!=now.dir&&now.dir!=-)//方向发生变化就加一,但是是第一步的时候并不算是转折
next.step++;
if ((next.x<=n&&next.x>=)&&(next.y<=m&&next.y>=)&&(map[next.x][next.y]==||(next.x==ex&&next.y==ey)))
{
if (next.step<)
{
if (next.step<visit[next.x][next.y]) //让visit数组保存的是到每一点的最小转折次数
{
visit[next.x][next.y]=next.step;
Q.push(next);
}
}
}
}
}
return ;
}
int main()
{
int i,j,t,sx,sy;
while (~scanf("%d %d",&n,&m))
{
if (n==&&m==)
break;
for (i=;i<=n;i++){
for (j=;j<=m;j++){
scanf("%d",&map[i][j]);
}
}
scanf("%d",&t);
while (t--)
{
cin>>sx>>sy>>ex>>ey;
if (sx==ex&&sy==ey)
{
printf("NO\n");
continue;
}
if (map[sx][sy]==||map[ex][ey]==||map[sx][sy]!=map[ex][ey])//这些特殊情况不要漏掉
{
printf("NO\n");
continue;
}
for(i = ; i <= n; i++)
for(j = ; j <= m; j++)
visit[i][j] = ; //初始化为一个很大的数
if (bfs(sx,sy)==)
printf("YES\n");
else
printf("NO\n");
} }
return ;
}
感觉这题深搜比广搜好想一些
无非就是多加了判断条件,注意回溯就行
code
#include<cstdio>
#include<cstring>
using namespace std;
int map[][],visit[][];
int n,m,ex,ey;
int dx[]={,,,-};
int dy[]={,,-,};
int ans;
void dfs(int fx,int fy,int dir,int step)
{
int x,y,i;
if (ans==)return ;
if (step>)return ;
if (step==&&fx-ex!=&&fy-ey!=)return ;
if (fx==ex&&fy==ey&&step<=)
{
ans=;
return ;
}
for (i=;i<;i++)
{
x=fx+dx[i];
y=fy+dy[i];
if (y<=||y>m||x<=||x>n)continue;
if (x==ex&&y==ey)
;
else if (map[x][y]!=)
continue;
if (visit[x][y]!=)continue;
//if (step>=3)continue;
if (dir!=i&&dir!=-)
step++;
visit[x][y]=;
dfs(x,y,i,step);
visit[x][y]=; //注意回溯,step也要回溯
if (i!=dir&&dir!=-)
step--;
}
}
int main()
{
int i,t,j,sx,sy;
while (~scanf("%d %d",&n,&m))
{
if (n==&&m==)
break;
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
scanf("%d",&map[i][j]);
}
scanf("%d",&t);
while (t--)
{
memset(visit,,sizeof(visit));
scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
if (sx==ex&&sy==ey)
{
printf("NO\n");
continue;
}
if (map[sx][sy]!=map[ex][ey]||map[sx][sy]==||map[ex][ey]==)
{
printf("NO\n");
continue;
}
ans=;
visit[sx][sy]=;
dfs(sx,sy,-,); if (ans==)
printf("YES\n");
else
printf("NO\n");
}
}
return ;
}