牛客网——wyh的迷宫

题目

给你一个n*m的迷宫，这个迷宫中有以下几个标识：

s代表起点

t代表终点

x代表障碍物

.代表空地

现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。
题目传送门

思路

也就是一道广搜题，简单题，只要注意搜索条件就好了，注意剪枝。基本模板跟许多迷宫题目都是一样的，不再重复赘述思路。

代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point{
    int x;
    int y;
}
public class Main {
    static int T;//测试组数
    static int n;//行
    static int m;//列
    static boolean flag;

    //开始搜索坐标
    static int start_x;
    static int start_y;
    static Queue<Point> queue=new LinkedList();
    static char[][] map = new char[510][510];
    static int visited[][]=new int[510][510];

    //方向数组，右下左上
    static int d_x[]={0,1,0,-1};
    static int d_y[]={1,0,-1,0};
    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        T=reader.nextInt();//测试组数
        for (int g=0;g<T;++g)//循环多少次
        {
            n=reader.nextInt();//行数
            m=reader.nextInt();//列数
            flag=false;
            String blank=reader.nextLine();//接收上面的回车符
            for (int i=0;i<n;++i)
            {
                String test=reader.next();
                char temp;
                for (int j=0;j<m;++j)
                {
                    temp=test.charAt(j);
                    map[i][j]=temp;
                    if (temp=='s')
                    {
                        start_x=i;
                        start_y=j;
                    }
                    visited[i][j]=0;//初始化标记数组
                }
            }
            Point start=new Point();
            start.x=start_x;
            start.y=start_y;
            visited[start_x][start_y]=1;//已访问
            queue.offer(start);
            while (!queue.isEmpty())
            {
                int x=queue.peek().x;
                int y=queue.peek().y;
                if (map[x][y]=='t')
                {
                    flag=true;
                    break;
                }
                for (int i=0;i<=3;++i)
                {
                    int temp_x=x+d_x[i];
                    int temp_y=y+d_y[i];
                    if (check(temp_x,temp_y))
                    {
                        Point temporary=new Point();
                        temporary.x=temp_x;
                        temporary.y=temp_y;
                        visited[temp_x][temp_y]=1;
                        queue.offer(temporary);
                    }
                }
                queue.poll();
            }
            if (flag==true)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
    //可达且没有被访问过
    public static boolean check(int a,int b)
    {
        return a>=0 && a<n && b>=0 && b<m &&(map[a][b]=='t' || map[a][b]=='.' ) && visited[a][b]==0;
    }
}

结果

简单题，并没有啥。。