走迷宫(BFS)

走迷宫(BFS)

走迷宫

给定一个 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++

代码语言：javascript代码运行次数：0运行复制

#include<iostream>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

ct int  = 110;

int n, m;
int g[][];  // 记录输入的矩阵
int d[][];  // 记录当前的距离	
PII q[ * ]; // 这里是数组来模拟队列

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

代码语言：javascript代码运行次数：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  = 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};
		(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)
				{
					(new Pair(x, y));
					d[x][y] = d[pair.x][pair.y] + 1;
				}
			}
		}
		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 5 输出样例：

提交代码

代码语言：javascript代码运行次数：0运行复制

#include<bits/stdc++.h>
using namespace std;
ct int  = 100010;

int a[], s[];
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;
}

代码语言：javascript代码运行次数：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 = ();
        int [] a = new int [n + 10];
        int [] s = new int [n + 10];
        int res = 0;
        for (int i = 0; i < n; ++ i) a[i] = ();
        for (int i = 0, j = 0; i < n; ++ i)
        {
            s[a[i]] ++;
            while(s[a[i]] > 1)
            {
                s[a[j]] --;
                j ++;
            }
            res = (res, i - j + 1);
        }
        println(res);
    }
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：202-01-20，如有侵权请联系 cloudcommunity@tencent 删除前往查看算法int队列数据数组