qq_27075621 于 2016.05.04 16:58 提问

hdu1175连连看广搜WA，各大神走过路过看一看啊~

package cn.hncu.search;

import java.util.Scanner;

public class P1175Bfs {
static int[][] map;
static int[][] visited;
static int eh,el;//终点行列
static int h,l;//输入数据时限制的行列

``````private static void bfs(int ch, int cl) {//传入当前行列数
int[][] dir={
{0,1},  //向右走
{1,0},  //向下走
{0,-1}, //向左走
{-1,0}  //向上走
};
int nh,nl;   //下一行,下一列
Queue queue=new Queue();
queue.push(ch, cl);
while (!queue.isNull()) {
Node node=queue.pop();
if (node.x==eh&&node.y==el) {            //发现目标
if (getTurnNum(queue)<=2) {
System.out.println("YES");
return;
}else{
System.out.println("NO");
return;
}
}
for (int i = 0; i < 4; i++) {
nh=node.x+dir[i][0];
nl=node.y+dir[i][1];
if (nh<1||nh>h||nl<1||nl>l) {
continue;
}
if ((map[nh][nl]==0&&visited[nh][nl]==0)||(nh==eh&&nl==el)) {
visited[nh][nl]=1;
queue.push(nh, nl);
}
}
}
}

private static int getTurnNum(Queue queue) {
Node[] nodes=queue.nodes;
int tail=queue.tail;
int turn=0;
for (int i = tail-1; i >= 3; i--) {
if (((nodes[i].x-1)==nodes[i-2].x&&(nodes[i].y-1)==nodes[i-2].y)      //爷爷节点的坐标是左上角，左下角，右上角，右下角
||((nodes[i].x-1)==nodes[i-2].x&&(nodes[i].y+1)==nodes[i-2].y)
||((nodes[i].x+1)==nodes[i-2].x&&(nodes[i].y-1)==nodes[i-2].y)
||((nodes[i].x+1)==nodes[i-2].x&&(nodes[i].y+1)==nodes[i-2].y)) {
turn++;
}
}
return turn;
}

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while (sc.hasNext()) {
//初始化数据
h=sc.nextInt();
l=sc.nextInt();
if ((h==0&&l==0)||(h==1&&l==1)) {
return;
}
map=new int[h+1][l+1];
visited=new int[h+1][l+1];

for (int i = 1; i <= h; i++) {
for (int j = 1; j <= l; j++) {
map[i][j]=sc.nextInt();
}
}

//输入测试数据
int q=sc.nextInt();
while (q-->0) {
int sh=sc.nextInt();
int sl=sc.nextInt();
eh=sc.nextInt();
el=sc.nextInt();
if (map[sh][sl]!=map[eh][el]) {
System.out.println("NO");
continue;
}
if (map[sh][sl]==0||map[eh][el]==0) {
System.out.println("NO");
continue;
}
if ((sh==eh)&&(sl==el)) {
System.out.println("NO");
continue;
}
visited[sh][sl]=1;
bfs(sh,sl);
}
}

}
``````

}

class Queue{
Node[] nodes=new Node[1000000];
int tail=1;
int turn;

``````public Queue(){
for (int i = 0; i < nodes.length; i++) {
nodes[i]=new Node();
}
}

public void push(int h,int l){
if (tail<nodes.length) {
nodes[tail].x=h;
nodes[tail].y=l;
tail++;
}
}

public Node pop(){
Node node=new Node();
return node;
}
return null;
}

public boolean isNull(){
return true;
}
return false;
}
``````

}

//封装节点的行列
class Node{
int x;
int y;
}

1个回答

CSDNXIAON   2016.05.04 17:02

HDU 1175 连连看（DFS）
hdu1175连连看（广搜）
hdu 1175 连连看（广搜）
----------------------同志你好，我是CSDN问答机器人小N，奉组织之命为你提供参考答案，编程尚未成功，同志仍需努力！