本文主要是介绍连连看 连线算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先得到所有路径，暑假开发android连连看时再用。
package com.test.action;
class Point
{
int x,y;//坐标
int t;//拐点个数
Point preturn;//上一个拐点
public Point(int xx,int yy,int tt,Point turnPoint)
{
x=xx;
y=yy;
t=tt;
preturn=turnPoint;
}
}
public class DFS
{
static int m=12,n=18,kinds=0;
static int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
public static void dfs(boolean vis[][],Point start,Point end)
{
if(start.t>2) return;
if(start.x==end.x && start.y==end.y)
{
kinds++;
System.out.print("[ "+start.x+" "+start.y+" "+start.t+"]");
while(start.preturn!=null)
{
System.out.print("<--[ "+start.preturn.x+" "+start.preturn.y+" "+start.preturn.t+"]");
start=start.preturn;
}
System.out.println();
System.out.println("*****************************************");
return;
}
else
{
for(int i=0;i<4;i++)
{
int xx=start.x+dir[i][0];
int yy=start.y+dir[i][1];
if(xx>=0 && xx<=m+1 && yy>=0 && yy<=n+1 &&!vis[xx][yy])
{
Point temp=new Point(xx,yy,start.t,start.preturn);
if(start.preturn==null) temp.preturn=start;
else if(start.preturn.x!=xx && start.preturn.y!=yy) {temp.t+=1;temp.preturn=start;}
vis[xx][yy]=true;
dfs(vis,temp,end);
vis[xx][yy]=false;
}
}
}
}
public static void main(String args[])
{
boolean vis[][]=new boolean[m+2][n+2];//障碍物
// vis[4][1]=true;
// vis[3][4]=true;
vis[5][18]=true;
vis[12][17]=true;
vis[2][17]=true;
Point start=new Point(2,2,0,null);
Point end=new Point(12,18,0,null);
vis[2][2]=true;
dfs(vis,start,end);
System.out.println(kinds);
}
}
广搜。
package com.test.action;
import java.util.LinkedList;
import java.util.Queue;
public class BFS
{
static int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};
public static boolean bfs(int m,int n,Point start,Point end)
{
boolean vis[][]=new boolean[m+2][n+2];
// vis[4][1]=true;
// vis[3][4]=true;
// vis[4][3]=true;
// vis[1][5]=true;
vis[2][17]=true;
Queue<Point> Q=new LinkedList<Point>();
Q.add(start);
vis[start.x][start.y]=true;
while(!Q.isEmpty())
{
Point q=Q.poll();
int x=q.x;
int y=q.y;
int t=q.t;
Point pre=q.preturn;
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(xx>=0 && xx<=m+1 && yy>=0 && yy<=n+1 &&!vis[xx][yy])
{
Point temp=new Point(xx,yy,t,pre);
vis[xx][yy]=true;
if(pre==null) temp.preturn=q;
else if(pre.x!=xx && pre.y!=yy) {temp.t+=1;temp.preturn=q;};
System.out.print("[ "+temp.x+" "+temp.y+" "+temp.t+"]");
if(pre!=null)System.out.println(" 转弯点： ["+pre.x+" "+pre.y+"]");
else System.out.println(" 转弯点： ["+start.x+" "+start.y+"]");
if(temp.x==end.x && temp.y==end.y )
{
System.out.print("[ "+temp.x+" "+temp.y+" "+temp.t+"]");
while(temp.preturn!=null)
{
System.out.print("<--[ "+temp.preturn.x+" "+temp.preturn.y+" "+temp.preturn.t+"]");
temp=temp.preturn;
}
System.out.println();
// return true;
}
Q.add(temp);
}
}
}
return false;
}
public static void main(String[] args)
{
Point start=new Point(2,2,0,null);
Point end=new Point(12,18,0,null);
bfs(12,18,start,end);
}
}
这篇关于连连看 连线算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
