Java实现dfs模版

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java实现dfs模版，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2744字，纯文字阅读大概需要4分钟。

内容图文

以走迷宫为例   0表示不可走  1表示可走  

给出地图 以及始末位置  判断是否能到达

import java.lang.reflect.Array;
import java.util.*;


public class main {
	
	public static int n,m;
	public static int mp[][]=new int[1000][1000]; //存储地图信息 1可走，0不可走；
	public static int d[][]= new int[][] {{0,-1},{-1,0},{0,1},{1,0}};//存储要移动的方向
	public static int vis[][]=new int[1000][1000];	//记录该点是否以被访问
	public static int x1,y1,x2,y2; //记录始末位置
	public static int flag=0;
	public static void dfs(int x,int y) {
		if(x==x2&&y==y2) { //到达终点
			flag=1;
			System.out.println("可以通过");
			return;
		}
		for(int i=0;i<4;i++) {//遍历四个方向
			int xx,yy;
			xx=x+d[i][0];
			yy=y+d[i][1];
			//判断下一步是否可以走，一方面判断路是否可走，另一方面判断自己是否走过这条路；
			if(vis[xx][yy]==0&&mp[xx][yy]==1&&x>0&&x<=n&&y>0&&y<=m) {
				vis[xx][yy]=1;//标记访问的点
				dfs(xx,yy);
			}
		}
	}
	public static void main(String args[]) {
		Scanner cin=new Scanner(System.in);
		n=cin.nextInt();
		m=cin.nextInt();
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				mp[i][j]=cin.nextInt();
			}
		}
		x1=cin.nextInt();
		y1=cin.nextInt();
		x2=cin.nextInt();
		y2=cin.nextInt();
		vis[x1][y1]=1; //标记起始点  ，这个别忘了
		dfs(x1,y1);
		if(flag==0) {
			System.out.println("不可通过");

		}
	}
}

输入样例

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

样例输出

可以通过

例题  https://www.luogu.com.cn/problem/P1238

题解： 注意移动方向  的优先顺序：左上右下

import java.lang.reflect.Array;
import java.util.*;

class node{
	private int x,y;
		public int getXX() {
		return x;
	}
	public int getYY() {
		return y;
	}
	public void setXX(int x) {
		this.x=x;
	}
	public void setYY(int y) {
		this.y=y;
	}
}

public class main {
	
	public static int n,m;
	public static int mp[][]=new int[1000][1000];
	public static int d[][]= new int[][] {{0,-1},{-1,0},{0,1},{1,0}};
	public static int vis[][]=new int[1000][1000];
	public static node ans[]=new node[1008611];
	
	public static int cnt=0,flag=0;
	public static int x1,y1,x2,y2;
	public static void dfs(int x,int y) {
		if(x==x2&&y==y2) {
			flag=1;
			System.out.print("("+x1+","+y1+")"+"->");
			for(int i=0;i<cnt-1;i++) {
				System.out.print("("+ans[i].getXX()+","+ans[i].getYY()+")->");
			}
			System.out.println("("+x2+","+y2+")");
			return;
		}
		for(int i=0;i<4;i++) {
			int xx,yy;
			xx=x+d[i][0];
			yy=y+d[i][1];
			if(vis[xx][yy]==0&&mp[xx][yy]==1) {
				vis[xx][yy]=1;
				ans[cnt].setXX(xx);
				ans[cnt].setYY(yy);
				cnt++;
				dfs(xx,yy);
				vis[xx][yy]=0;
				cnt--;
			}
		}
	}
	public static void main(String args[]) {
		Scanner cin=new Scanner(System.in);
		n=cin.nextInt();
		m=cin.nextInt();
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				mp[i][j]=cin.nextInt();
			}
		}
		x1=cin.nextInt();
		y1=cin.nextInt();
		x2=cin.nextInt();
		y2=cin.nextInt();
		for(int i=0;i<1008610;i++) {
			ans[i]=new node();
		}
		vis[x1][y1]=1;
		dfs(x1,y1);
		if(flag==0) {
			System.out.println(-1);
		}
	}
}

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的Java实现dfs模版全部内容，希望文章能够帮你解决Java实现dfs模版所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端