2 qq 27075621 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 head=1;
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(){
    if (head<nodes.length) {
        Node node=new Node();
        node=nodes[head];
        head++;
        return node;
    }
    return null;
}

public boolean isNull(){
    if (head==tail) {
        return true;
    }
    return false;
}

}

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

1个回答

CSDNXIAON
CSDNXIAON   2016.05.04 17:02

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!