没有合适的资源？快使用搜索试试~ 我知道了~

首页算法-图论模板（java实现）

算法-图论模板（java实现）

java

算法

图论

数据结构

需积分: 28 160 浏览量更新于2023-05-25 评论 1 收藏 1.08MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

31页

经典图论算法题的模板实现，包括最短路，宽搜深搜，拓扑序列，二分图等问题。作者参加算法比赛的利器。现在免费送给你。适合参加蓝桥杯、PAT等算法比赛或者面试的图论基础知识。

资源详情

资源评论

资源推荐

宽搜和深搜

AcWing.843-皇后问题

题目描述

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后

都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空， Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

题解

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main2 {

static boolean col[],dg[],udg[]; // 列、正截距、反截距（利用斜率相同，同一条线上的截

距也相同）

static char g[][];

static int N = 20;

AcWing.844-走迷宫

题目描述

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

表示不可通过的墙壁。

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

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

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

输入格式

第一行包含两个整数 n和 m。

public static void main(String[] args) throws Exception, IOException {

BufferedReader bf = new BufferedReader(new

InputStreamReader(System.in));

int n =Integer.parseInt(bf.readLine());

g = new char[n][n];

for(int i=0;i<n;i++) {

for(int j=0;j<n;j++) {

g[i][j]='.';

}

col = new boolean[N];

dg = new boolean[N];

udg = new boolean[N];

dfs(0,n);

}

public static void dfs(int u,int n) {

if(u==n) {

for(int i=0;i<n;i++) {

for(int j=0;j<n;j++) {

System.out.print(g[i][j]);

}

System.out.println();

}

System.out.println();

return;

}else {

for(int i=0;i<n;i++) {

if(!col[i]&&!dg[u+i]&&!udg[n-u+i]) {

g[u][i] ='Q';

col[i] = dg[u+i] = udg[n-u+i]=true;

dfs(u+1,n);

g[u][i] ='.';

col[i] = dg[u+i] = udg[n-u+i]=false;

}

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

输出格式

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

输入样例：

输出样例：

题解

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

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

class Pair {

int x;

int y;

public Pair(int x, int y) {

this.x = x;

this.y = y;

}

public class Main {

static int[] dx = { 1, -1, 0, 0 };

static int[] dy = { 0, 0, 1, -1 };

static int[][] map = null;

static int[][] d = null;

static int n, m;

 

public static void main(String[] args) throws Exception {

BufferedReader bf = new BufferedReader(new

InputStreamReader(System.in));

String str[] = bf.readLine().split(" ");

n = Integer.parseInt(str[0]);

m = Integer.parseInt(str[1]);

map = new int[n][m];

d = new int[n][m];

for (int i = 0; i < n; i++) {

String s[] = bf.readLine().split(" ");

for (int j = 0; j < m; j++) {

map[i][j] = Integer.parseInt(s[j]);

}

System.out.println(bfs());

AcWing.845-八数码

题目描述

在一个 3×3 的网格中，1∼8这 8个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

}

 

public static int bfs() {

Queue<Pair> q = new LinkedList<>();

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;

}

   return d[n - 1][m - 1];

}

1 2 3

x 4 6

7 5 8

1 2 3

4 5 6

7 8 x

1 2 3  1 2 3  1 2 3  1 2 3

x 4 6  4 x 6  4 5 6  4 5 6

7 5 8  7 5 8  7 x 8  7 8 x

输入占一行，将3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

则输入为： 1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

题解

1 2 3

x 4 6

7 5 8

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Queue;

public class Main {

static int dx[]= {1,0,-1,0},dy[]= {0,1,0,-1};

public static void main(String[] args) throws Exception {

BufferedReader bf = new BufferedReader(new

InputStreamReader(System.in));

String str[] = bf.readLine().split(" ");

String start = "";

for(int i=0;i<str.length;i++) {

start+=str[i];

}

System.out.println(bfs(start));

}

 

public static int bfs(String start) {

Queue<String> q = new LinkedList<>();

HashMap<String,Integer> d = new HashMap<>();

q.offer(start);

d.put(start, 0);

String end = "12345678x";

while(!q.isEmpty()) {

String s = q.poll();

int distance = d.get(s);

if(s.equals(end)) {

return distance;

}

int k=s.indexOf("x");

int x = k/3,y = k%3;

for(int i=0;i<4;i++) {

int a = x+dx[i],b=y+dy[i];

if(a>=0&&a<3&&b>=0&&b<3) {

         char[] arr = s.toCharArray();

         swap(arr, k, a * 3 + b);

         String str = new String(arr);

         if (d.get(str) == null) {

剩余30页未读，继续阅读

杜柠函

粉丝: 252
资源: 1

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

算法-图论模板（java实现）

评论0

会员权益专享

最新资源

算法-图论模板（java实现）

评论0

ACM图论模板合集.pdf

diffie-hellman算法java实现

dp,douglas-peucker算法java实现

国密算法--Openssl 实现国密算法（加密和解密）

装载问题-分支限界算法-java实现

算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索

非常全的c语言常用算法

算法模板汇总 java

kMP算法JavakMP算法JavakMP算法JavakMP算法Java

KNN的java 实现

k-means聚类算法java实现

bellman-ford算法java

miller-rabin算法java

蓝桥杯算法模板java

c算法大全常用c语言算法，包括数论算法，图论算法、排序算法、高精度计算、树的遍历算法等等

Java点线面算法----点线面关系

diffie-hellman算法 java

IT面试笔试-各种排序算法Java实现

卷积码的MAP算法-最大后验概率算法

会员权益专享

最新资源