学步园

bfs()搜索，关键在于用mark[][]去标记时间

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
int sx,sy,ex,ey,n,m;
int mark[9][9],map[9][9],dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node{
	int x,y,time,step;
};
int overmap(int x,int y)
{
	if(x<0||x>=n||y<0||y>=m)return 1;
	else return 0;
}
int bfs()
{
	memset(mark,0,sizeof(mark));//注意清零	
        queue<node>q;
	node first,next;
	first.x=sx;
	first.y=sy;
	first.time=6;
	first.step=0;
	q.push(first);
	mark[first.x][first.y]=6; //注意初始时间赋值
	while(!q.empty())
	{
	    first=q.front();
		q.pop();
		if(first.x==ex&&first.y==ey)
			return first.step;
		if(map[first.x][first.y]==4)
		{
			first.time=6;
			mark[first.x][first.y]=6;
		}
		for(int i=0;i<4;i++)
		{
			next.x=first.x+dir[i][0];
			next.y=first.y+dir[i][1];
			next.step=first.step+1;
			next.time=first.time-1;
			if(overmap(next.x,next.y)||map[next.x][next.y]==0||next.time<=0)
				continue;
			if(mark[next.x][next.y]<next.time)//如果四周时间小于当前时间，就将当前时间赋给mark[][]
			{
				mark[next.x][next.y]=next.time;
				q.push(next);
			}
		}
	}
	return -1;
//如果没有返回-1
}
int main()
{
	int k,i,j;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			{
				scanf("%d",&map[i][j]);
				if(map[i][j]==2)
				{sx=i;sy=j;}
				if(map[i][j]==3)
				{ex=i;ey=j;}
			}
			printf("%d\n",bfs());
	}
	return 0;
}

 只用mark[][]去标记就可以

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int map[9][9],mark[9][9],sx,sy,ex,ey,line,row;
int dir[4][2]={1,0,-1,0,0,-1,0,1};
struct node
{
    int x,y,step;
};
int overmap(int x,int y)
{
    if(x<0||x>=line||y<0||y>=row) return 1;
    else return 0;
}
int bfs()
{
    memset(mark,0,sizeof(mark));
    int ltime;
    queue<node>q;
    node first,next;
    first.x=sx;
    first.y=sy;
    first.step=0;
    q.push(first);
    mark[first.x][first.y]=6;
    while(!q.empty())
    {
        first=q.front();q.pop();
        if(first.x==ex&&first.y==ey)
        return first.step;
        if(map[first.x][first.y]==4)
        {
            mark[first.x][first.y]=6;
        }
        for(int i=0;i<4;i++)
        {
            next.x=first.x+dir[i][0];
            next.y=first.y+dir[i][1];
            next.step=first.step+1;
            ltime=mark[first.x][first.y]-1;
            if(overmap(next.x,next.y)||map[next.x][next.y]==0||ltime<=0)
            continue;
            if(mark[next.x][next.y]<ltime)
            {
                mark[next.x][next.y]=ltime;
                q.push(next);
            }
        }

    }
    return -1;
}
int main()
{
    int cases,i,j;
    scanf("%d",&cases);
    while(cases--)
    {
       scanf("%d%d",&line,&row);
       for(i=0;i<line;i++)
       {
           for(j=0;j<row;j++)
           {
               scanf("%d",&map[i][j]);
               if(map[i][j]==2)
               {sx=i;sy=j;}
               if(map[i][j]==3)
               {ex=i;ey=j;}
           }
       }
       printf("%d\n",bfs());
    }
    return 0;
}