走迷宫(BFS)

叁歲伎倆 2024-03-30 11:09 65阅读 0赞

## 走迷宫 ##

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式  
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式  
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围  
1≤n,m≤100  
输入样例：  
5 5  
0 1 0 0 0  
0 1 0 1 0  
0 0 0 0 0  
0 1 1 1 0  
0 0 0 1 0  
输出样例：  
8

### C++ ###

#include<iostream>
    #include<cstring>
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 110;
    
    int n, m;
    int g[N][N];  // 记录输入的矩阵
    int d[N][N];  // 记录当前的距离	
    PII q[N * N]; // 这里是数组来模拟队列
    
    int bfs()
    {
        
    	int hh = 0, tt = 0;  // 数组的头和尾
    	q[0] = {
        0, 0};		 // 初始化 最开始还没有走的 点的坐标是（x, y）= （0，0）
    						 // 把这个第一个坐标入队
    	memset(d, -1, sizeof(d)); // 把这个当前距离的数组初始化为-1 代表还没有走过
    	d[0][0] = 0;		// 这个是最开始第一个点还没有走过 所以距离是0
     
    	int dx[4] = {
         -1, 0, 1, 0 }; // 这里记录了4个方向的坐标(-1,0),(1,0),(0,1),(0,-1)
    	int dy[4] = {
         0, 1, 0, -1 }; // 通过分别对四个方向坐标的相加 判断 可以知道是否应该 往这个方向走
    	
    	while (hh <= tt) // 判断队列是否为空
    	{
        
    		auto t = q[hh++]; // 取队首， 并队首元素出队
    
    		for (int i = 0; i < 4; i++)
    		{
        
    			int x = t.first + dx[i], y = t.second + dy[i];  // 枚举向每个方向移动的情况
    
    			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) 
    				// 这里的判断条件的含义是 尝试这个当前这个方向之后的得到的 x, y值
    				// 没有过边界 而且新的这条路g[x][y] == 0表示可以走
    				// d[x][y] == -1表示这条路还没有走过 
    			{
        
    				d[x][y] = d[t.first][t.second] + 1; // 然后路的长度 + 1
    				q[++tt] = {
        x, y};  // 把新的坐标入队
    			}
    		}
    	}
    	return d[n - 1][m - 1];
    	
    }
    int main()
    {
        
    	cin >> n >> m;
    	for (int i = 0; i < n; ++i)
    	{
        
    		for (int j = 0; j < m; ++j)
    		{
        
    			cin >> g[i][j];
    		}
    	}
    	cout << bfs() << endl;
    	return 0;
    }

### Java ###

import java.io.*;
    import java.util.*;
    
    class Pair{
        
    	int x;
    	int y;
    	public Pair(int x, int y)
    	{
        
    		this.x = x;
    		this.y = y;
    	}
    }
    public class Main
    {
        	
    	static int n, m;
    	static int N = 110;
    	static int [][] map = null;
    	static int [][] d = null;
    	static void bfs()
    	{
        
    		Queue<Pair> q = new LinkedList<Pair>();
    		int [] dx = {
        -1, 0, 1, 0};
    		int [] dy = {
        0, 1, 0, -1};
    		q.offer(new Pair(0, 0));
    		while(!q.isEmpty())
    		{
        
    			Pair pair = q.poll();
    			if (pair.x == n - 1 && pair.y == m - 1) break;
    			for (int i = 0; i < 4; ++ i)
    			{
        
    				int x = pair.x + dx[i];
    				int y = pair.y + dy[i];
    				if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0 && d[x][y] == 0)
    				{
        
    					q.offer(new Pair(x, y));
    					d[x][y] = d[pair.x][pair.y] + 1;
    				}
    			}
    		}
    		System.out.println(d[n - 1][m - 1]);
    	}
    	public static void main(String[] args) throws IOException 
    	{
        
    		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    		String [] nums = reader.readLine().split(" ");
    		n = Integer.parseInt(nums[0]);
    		m = Integer.parseInt(nums[1]);
    		map = new int [n][m];
    		d = new int [n][m];
    		for (int i = 0; i < n; ++ i)
    		{
        
    			String [] inputs = reader.readLine().split(" ");
    			for (int j = 0; j < m; ++ j)
    			{
        
    				map[i][j] = Integer.parseInt(inputs[j]);
    			}
    		}
    		bfs();
    	}
    }

**每天一道算法题**

## 最长连续不重复子序列 ##

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式  
第一行包含整数 n。

第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。

输出格式  
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围  
1≤n≤105  
输入样例：  
5  
1 2 2 3 5  
输出样例：  
3

**提交代码**

#include<bits/stdc++.h>
    using namespace std;
    const int N = 100010;
    
    int a[N], s[N];
    int n, res;
    
    int main()
    {
        
        cin >> n;
        for (int i = 0; i < n; ++ i) cin >> a[i];
        for (int i = 0, j = 0; i < n; ++ i)
        {
        
            s[a[i]] ++; // 记录下a[i]出现的次数
            while(s[a[i]] > 1)   // 一点碰见两个重复的元素后
            {
          
                s[a[j]] --;  // 这里要主要的一点是这个算法是没有回溯的
                             // 不要被for循环里面的条件误导以为会回溯、
                             // 现在遇到两个相同的元素了
                             // ！！！ 现在是这个算法最厉害的地方 
                             // 这个j代表的是 j可以到达最左的地方 所以在j左边的
                             // 元素的个数就需要都-- 这点很妙
                             // 每次求的是 j到i之间的符合条件的最大值
                j ++;        // 然后j++
            }
            res = max(res, i - j + 1);  // 这个res的含义是 在i这个位置、
            // 可以达到的符合题目条件的最大长度
        }
        cout << res;
        return 0;
    }

import java.io.*;
    import java.util.*;
    
    public class Main
    {
        
        public static void main(String[] args) throws IOException{
        
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int [] a = new int [n + 10];
            int [] s = new int [n + 10];
            int res = 0;
            for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
            for (int i = 0, j = 0; i < n; ++ i)
            {
        
                s[a[i]] ++;
                while(s[a[i]] > 1)
                {
        
                    s[a[j]] --;
                    j ++;
                }
                res = Math.max(res, i - j + 1);
            }
            System.out.println(res);
        }
    }