Search for the element of the template question dfs|bfs can be.
Title gate
Minimum step number
Time limit: 3000 ms | memory limit: 65535 KB
describe
There is a maze with 0-8 rows and 0-8 columns:

1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,1

0 for roads, 1 for walls.
Now input the coordinates of a road as the starting point, and input the coordinates of a road as the end point. How many steps can you take to get from the starting point to the end point? (Note: one step refers to walking from one coordinate point to its upper and lower left and right adjacent coordinate points, such as from (3, 1) to (4, 1).)
input
Enter an integer n (0-100) in the first line to indicate that there are n groups of data;
Then, there are four integers a,b,c,d (0 < = a,b,c,d < = 8) in n rows, which respectively represent the row and column at the beginning and the row and column at the end.
output
Output at least a few steps.
sample input
2
3 1 5 7
3 1 6 7
sample output
12
11

dfs

#include<stdio.h>
const int maxn=10000;
int sx,sy,ex,ey;
int map[9][9]={
    1,1,1,1,1,1,1,1,1,
 1,0,0,1,0,0,1,0,1,
 1,0,0,1,1,0,0,0,1,
 1,0,1,0,1,1,0,1,1,
 1,0,0,0,0,1,0,0,1,
 1,1,0,1,0,1,0,0,1,
 1,1,0,1,0,1,0,0,1,
 1,1,0,1,0,0,0,0,1,
 1,1,1,1,1,1,1,1,1
};
int vis[9][9];
int d[4][2]={0,1,0,-1,1,0,-1,0};
int ans;
void dfs(int x,int y,int c)
{
    if(map[x][y])
    return ;
    c++;
    if(x==ex&&y==ey)
    {
        if(c<ans)
        ans=c;
        return ;
    }
    map[x][y]=1;
    dfs(x,y+1,c);
    dfs(x+1,y,c);
    dfs(x-1,y,c);
    dfs(x,y-1,c);
    map[x][y]=0;
}
int main()
{
        int n;
    scanf("%d",&n);
    while(n--)
    {
        int c=0;
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        ans=maxn;
        dfs(sx,sy,c);
        printf("%d\n",ans-1);
    }
return 0;
}

bfs

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int map[9][9]={
1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,
};
struct node
{
    int x,y,step;
};
bool vis[9][9];
int x,y,ex,ey;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int BFS(){
    node s;
    s.x=x,s.y=y,s.step=0;
    vis[x][y]=true;
    queue<node>q;
    q.push(s);
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.x==ex&&now.y==ey)
        {
        return now.step;
        }
        for(int i=0;i<4;i++)
        {
            node end;
            end.x=now.x+dx[i];
            end.y=now.y+dy[i];
            end.step=now.step;
            if(vis[end.x][end.y]==false&&map[end.x][end.y]==0)
            {
                vis[end.x][end.y]=true;
                end.step+=1;
                q.push(end);
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,false,sizeof(vis));
        scanf("%d%d%d%d",&x,&y,&ex,&ey);
        int ans=BFS();
        printf("%d\n",ans);
    }
return 0;
}