走迷宫(BFS)

#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;
}

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();
	}
}

#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);
    }
}