nyoj 58 最少步数（bfs）

╰半橙微兮° 2024-02-17 20:56 41阅读 0赞

### 最少步数 ###

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 4

描述

这有一个迷宫，有0~8行和0~8列：

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表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入

第一行输入一个整数n（0<n<=100），表示有n组测试数据;  
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
    3 1  5 7
    3 1  6 7

样例输出

12
    11

分析：简单bfs

AC代码：

#include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int g[10][10]={
    {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;
    	node(int x=0,int y=0):x(x),y(y){}
    }ns,nd;
    
    int d[10][10];
    int dir[][2]={
       {-1,0},{1,0},{0,1},{0,-1}};
    
    bool isValid(node& nt){
    	return nt.x>=0&&nt.x<=8 && nt.y>=0&&nt.y<=8;
    }
    
    void bfs(){
    	memset(d,-1,sizeof(d));
    	d[ns.x][ns.y]=0;
    	queue<node>q;
    	q.push(ns);
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		
    		if(u.x==nd.x && u.y==nd.y){
    			printf("%d\n",d[u.x][u.y]);
    			return ;
    		}
    		
    		for(int i=0;i<4;i++){
    			node v=node(u.x+dir[i][0],u.y+dir[i][1]);
    			if(isValid(v) && d[v.x][v.y]==-1 && (g[v.x][v.y]==0 || v.x==nd.x&&v.y==nd.y)){
    				q.push(v);
    				d[v.x][v.y]=d[u.x][u.y]+1;
    			}
    		}
    	}
    }
    int main(){
    	int n;
    	scanf("%d",&n);
    	while(n--){
    		int a,b,c,d;
    		scanf("%d%d%d%d",&a,&b,&c,&d);
    		ns.x=a,ns.y=b;
    		nd.x=c,nd.y=d;
    		bfs(); 
    	}
    	return 0;
    }