「javabfs」Javabfs与dfs

本篇文章给大家谈谈javabfs，以及Javabfs与dfs对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、分别用DFS和BFS算法给电脑设置AI(JAVA)
• 2、Java 鼠标控制人物移动，地图随人物移动
• 3、ACM学bfs dfs需要有什么基础，C++吗，还是Java
• 4、JAVA求10个景点间各个景点的最短路径 图随便话 距离随便 求代码
• 5、Java推箱子怎么写啊?

分别用DFS和BFS算法给电脑设置AI(JAVA)

有必胜策略的吧。。状态空间的上限是3^9也就是不到20000实际上没有这么多。所以直接采用BFS标记会比较好。算法的话就是填充表，把表（九个格子）填为必胜、必败，己胜，开始的时候全部标为必败，再从胜状态开始向回BFS（或者DFS也可以），己胜状态向回标的一定是败状态，必胜状态的上一状态为必败态，必败态的上一状态可能是必败或者必胜（这就是因为这家伙走错棋了所以要输！）

我的习惯。不写代码。没有意思。

Java 鼠标控制人物移动，地图随人物移动

去学习A星寻路，可以得到最短路径，其中也包括了绕开障碍物的代码，然后就是动画的图片切换了，如果说要地图跟随主角移动，那个应该是滚屏操作，也就是说你主角往右走，超过窗口或者屏幕（全屏）坐标一半的时候，地图整个往左移动，速度和主角的一样就出来效果了。如果你看不懂A星的话，那咂就给你一段BFS的C++语言代码，自己转换成JAVA代码写法（就是改些关键字，有不少经典的游戏算法都来自C/C++）就可以了，这个是简化版的A星寻路，一样可以找到最近的路径，你把path 这个路径记录下来再换算成像素位置就可以得到行走的具体步伐了...

#include "stdafx.h"

#include iostream

using namespace std;

const int rows = 10;//行数

const int cols = 10;//列数

const int nummax = 4;//每一步，下一步可以走的方向：4个

//四种移动方向(左、右、上、下)对x、y坐标的影响

//x坐标：竖直方向，y坐标：水平方向

const char dx[nummax] = {0,0,-1,1};

const char dy[nummax] = {-1,1,0,0};

//障碍表

char block[rows][cols] = {

0,1,0,0,0,0,0,0,0,0,

0,1,1,0,1,1,1,0,0,0,

0,0,0,0,0,0,0,0,0,0,

1,0,1,0,0,0,0,0,0,0,

0,0,0,0,0,0,1,1,1,0,

0,1,0,0,0,0,1,0,0,0,

0,0,0,0,0,0,1,1,0,1,

0,1,0,0,0,1,0,1,0,1,

0,1,1,1,0,0,0,1,0,1,

0,0,0,0,0,0,0,0,0,0,

};

char block2[rows][cols] = {

0,1,0,0,0,0,0,0,0,0,

0,1,1,0,1,1,1,0,0,0,

0,0,0,0,0,0,0,0,0,0,

1,0,1,0,0,0,0,0,0,0,

0,0,0,0,0,0,1,1,1,0,

0,1,0,0,0,0,1,0,0,0,

0,0,0,0,0,0,1,1,0,1,

0,1,0,0,0,1,0,1,0,1,

0,1,1,1,0,0,0,1,0,1,

0,0,0,0,0,0,0,0,0,0,

};

char path[rows][cols] = {0};//记录路径

int startX = 0,startY = 0;//起始点坐标

int endX = rows - 1,endY = cols - 1;//目标点坐标

//保存节点位置坐标的数据结构

typedef struct tagQNode{

char x,y;

int parentNode;//父节点索引

}QNode;

//打印路径

void printPath()

{

cout  ""  endl;

for (int i = 0;i  rows;++i)

{

for (int j = 0;j  cols;++j)

{

if (1 == path[i][j])

{

cout  "♀";

}

else if(block2[i][j]==0)

cout  "∷";

else if(block2[i][j]==1)

cout  "■";

}

cout  endl;

}

cout  endl;

cout  endl;

}

void BFS()

{

int num = rows * cols;

//利用数组来模拟队列

QNode *queue = (QNode *)malloc(num * sizeof(QNode));

//起始点入队列

queue[0].x = queue[0].y = 0;

queue[0].parentNode = -1;//起始点没有父节点

int front = 0,rear = 1;//队列的头和尾

while(front != rear)//队列不为空

{

for (int i = 0;i  nummax;++i)

{

    char nextX,nextY;//下一步的坐标

nextX = queue[front].x + dx[i];

nextY = queue[front].y + dy[i];

//下一个节点可行

if (nextX = 0  nextX  rows   nextY = 0  nextY  cols   0 == block[nextX][nextY])

{

    //寻找到目标点

if (nextX == endX  nextY == endY)

{

    //生成路径

path[nextX][nextY] = 1;

int ParIn = front;

while(ParIn != -1)

{

path[queue[ParIn].x][queue[ParIn].y] = 1;

ParIn = queue[ParIn].parentNode;

}

//printPath();

}

//入栈

queue[rear].x = nextX;

queue[rear].y = nextY;

queue[rear].parentNode = front;

++rear;

//标记此点已被访问

block[nextX][nextY] = 1;

}

}

++front;

}

free(queue);

}

int _tmain(int argc, _TCHAR* argv[])

{

BFS();

printPath();

system("pause");

    return 0;

}

ACM学bfs dfs需要有什么基础，C++吗，还是Java

bfs的话，要用到队列的思想的。

不过队列的思想讲起来，也很简单已接受，自己网上找一下就好了。

至于其他的除了queue以外的东西，比如你写的algorithm库函数的，跟bfs无关，可以不做了解。

至于dfs，只要懂递归就可以了。

建议先学dfs，再学bfs。

JAVA求10个景点间各个景点的最短路径 图随便话 距离随便 求代码

最有效，切不复杂的方法使用Breadth First Search (BFS). 基本代码如下（伪代码）。因为BFS不用递归，所以可能会有点难理解。

public Stack findPath(Vertex 起始景点, Vertex 目标景点){

Queue Vertex q = new QueueVertex();

s.enqueue(起始景点);

Vertex 当前位置;

while(!s.isEmpty()){

当前位置 = s.dequeue();

if (当前位置 == 目标景点) break;

for (每一个相邻于 当前位置 的景点 Vertex v){

if (!v.visited){

v.parent = 当前位置;

// 不是规定，不过可以节省一点时间

if (v == 目标景点){

current = v;

break;

}

s.enqueue(Vertex v);

v.visited = true;

}

}

}

Stack Vertex solution = new Stack Vertex();

Vertex parent = current;

while (parent != 起始景点){

solution.push(parent);

parent = current.parent;

}

for (graph中的每一个vertex) vertex.visited = false;

return solution(); // 其实这里建议用一个 Path 的inner class 来装所获得的路线

}

然后再 main 求每两个景点之间的距离即可

public static void main(String[] argv){

PathFinder pf = new PathFinder();

Stack[][] 路径 = new Stack[10][10];

for(int i=0; ipf.vertices.length; i++){

for(int j=i+1; jpf.vertices.length; j++){

Stack s = pf.findPath(pf.vertices[i], pf.vertices[j]);

路径[i][j] = s; 路径[j][i] = s; // 假设你的graph是一个undirected graph

}

}

// 这么一来就大功告成了！对于每两个景点n 与 m之间的最短路径就是在 stack[n][m] 中

}

还有一种方法就是用Depth First Search递归式的寻找路径，不过这样比较慢，而且我的代码可能会造成stack overflow

public Stack dfs(Vertex 当前景点，Vertex 目标景点){

if(当前景点 == 目标景点) return;

Stack solution = new Stack();

Stack temp;

for (相邻于 点钱景点 的每一个 Vertex v){

if (!v.visited){

v.visited = true;

temp = dfs(v, 目标景点);

// 抱歉，不记得是stack.size()还是stack.length()

if (solution.size() == 0) solution = temp;

else if(temp.size() solution.size()) solution = temp;

v.visited = false; 复原

}

}

return solution;

}

然后再在上述的Main中叫dfs...

参考：

Java推箱子怎么写啊?

这是我之前写的一篇java实现推箱子算法的文章，简单的给你看一下：

《推箱子游戏》是一款益智游戏，游戏目标是搬运工自己来找出到某个位置的最短路径，然后自己走过去。

地图是这个游戏中非常重要的一部分，关于地图的存储，因为有一部分元素是可以重叠放置的，所以用了一个类似二进制的存储方式，就是4种物件分别有是否存在状态，使得用一个数字可以表示多个物件。

1、是否存在目的地

2、是否存在箱子

3、是否存在人

4、是否存在墙壁

这样就解决了地图存储问题。使用short[][]就存下了。

一、在不移动箱子的情况下其实无论人在哪里对于map来说是没有影响的，所以填充可移动区域可以让需要存储地图的数量有一个大的下降。例如之前那副地图：

8888888

8103018

8002008

8320238

8012108

8403008

8888888

经过变换之后就成了：

8888888

8103018

8002008

8320238

8452108

8443008

8888888

这样就把存储量缩小了四分之三。至于怎样填充，相信对图论有一点了解的都可以随便想出方案，我这里用的是BFS。

话不多说，实现代码如下：

二、关于箱子的移动方式，直接用整幅地图的BFS搜索会比较靠谱。因为可以确定箱子的位置和在不移动箱子情况下人能到的位置，所以箱子可移动的位置也就能确定了，再加上之前存储的所有箱子的位置，这样就能计算出箱子每动作一次地图能更新的情况，一次BFS就是每个箱子往不同可移动位置进行一次移动。

三、结束搜索分为三种情况：

所有目的地被填充完毕-------计算完成退出程序。

有箱子被推到角落并且不是在目的地--------说明不是正确的路线，搜索不再往下走。

当前地图在以前已经被达成过--------说明是重复路线，搜索不再往下走。

四、关于地图的存储，用的是hashSet，并重写了equals和hashCode的实现，用来自动判断地图是否重复。（以此保证不重复）

最后完成地图显示问题，每个节点存储自己父亲节点的地址，当节点发现自己已经完成之后根据地址向上查找直到树顶，望采纳，谢谢。

关于javabfs和Javabfs与dfs的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。