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

问题描述

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;
}

解决方案

HDU 1175 连连看(DFS)
hdu1175连连看(广搜)
hdu 1175 连连看(广搜)

时间: 2024-10-05 15:19:34

hdu1175连连看广搜WA,各大神走过路过看一看啊~的相关文章

编程-大神们能帮我看下这个C里就多了这几行没多大关系的代码,就引发了异常断点?

问题描述 大神们能帮我看下这个C里就多了这几行没多大关系的代码,就引发了异常断点? 在第一张图里上一个cEx2数组输出正常,然后就经过了imper2的内存分配和赋值,不应该造成下面在cEx2[1]输出时引发的断点啊! 求解神们?查了一下午仍然没结果,只能求神了-- 解决方案 已解决,编译器问题好像.只要把malloc放到开头,就不会有这个问题. 求解释?表示不懂. 解决方案二: 多余了就把它删除了吧,可能是和你前面的代码发生冲突了-- 解决方案三: 希望能把问题描述清楚,这样大家才好帮你定位问题

初学者-各位大神,能不能帮看一下问题是在哪,一直提示错误,改了好多遍都没还对

问题描述 各位大神,能不能帮看一下问题是在哪,一直提示错误,改了好多遍都没还对 package jsp; public class Circle { double side; double areaperimeter; public void setCircle(double r){ side=r; } public double getCircle(){ return side; } public double getArea(){ area=Math.sqrt(3.14*side*side)

c++-求大神加注释,小弟看不懂

问题描述 求大神加注释,小弟看不懂 int main(){ cout<<""-----迷宫-----""< maze m; return 0;}maze::maze(){ int ij; cout cin>>Height>>Width; a = new int*[Height]; for(i = 0;i != Height;i++) { a[i] = new int[Width]; } rd = new Road*[Heig

xpath-求大神帮忙注释一下,看不懂

问题描述 求大神帮忙注释一下,看不懂 public String getMarketOrderType(String pMarket) { String xpath = DOUBLE_LEADING_SLASH + "HKSPOEPINT001"+ DOUBLE_LEADING_SLASH + "value"; return pathResolve(xpath).get(pMarket+"-order-type"); } 解决方案 public

求大神指教啊,linux看不出那到底哪里出问题了。。程序死了

问题描述 求大神指教啊,linux看不出那到底哪里出问题了..程序死了 #0 0x47f23c7c in _int_malloc () from /lib/libc.so.6 #1 0x47f25fb7 in malloc () from /lib/libc.so.6 #2 0x48729af7 in operator new(unsigned int) () from /usr/lib/libstdc++.so.6 #3 0x4870513b in std::string::_Rep::_S_

图片-前端大神、程序猿、看过来,这里的问题真精彩~

问题描述 前端大神.程序猿.看过来,这里的问题真精彩~ 我有一组ui li像这样: 代码1: <ui class="main_lower_ui"> <li>选集</li> <li class="selected">历史</li> </ui> 代码1效果图: 现在我想用jquery实现当我点击选集的时候 历史的字体颜色变回去 选集的颜色变浅色 像这样: 求解答~拜谢 解决方案 代码 $('.mai

iring i-树莓派大神求救,源码看不懂 啊

问题描述 树莓派大神求救,源码看不懂 啊 import com.pi4j.wiringpi.Spi; public class WiringPiSPIExample { // SPI operations public static byte WRITE_CMD = 0x40; public static byte READ_CMD = 0x41; @SuppressWarnings("unused") public static void main(String args[]) th

没学过java 我想自学求大神支招我该看什么书?

问题描述 最近想学点东西充实自己顺便找个工作想学JAVA大神给支支招我该看什么书,从哪学起,我学过一点C语言?????? 解决方案 解决方案二: 解决方案三:看jdk的jdoc解决方案四:java入门还是跟着视频走吧.java界比较权威的java编程思想和java核心技术都不适合初学者看百度下尚学堂马士兵或者圣思源张龙他们的视频都不错,建议楼主跟着他们入门.看完后可以看java编程思想或java核心技术,进行进阶提升.解决方案五:哦,视频很好,网上有很多java的视频的个人推荐斯坦福的那个jav

网页-html+css新手,大神们能帮看看这个布局怎么搞么

问题描述 html+css新手,大神们能帮看看这个布局怎么搞么 如图,这是我网页布局的草稿,具体应该怎么搞不太明白.能帮帮我么 解决方案 图片转过来啦 解决方案二: 在中间多加一个div用来装中间的三个div 解决方案三: 解决方案四: 上下两个div,一个float是top,一个bottom,中间那个用absolute的postion,自己用JavaScript去控制它的left和top,以及height,它里面套3个div,自己控制宽度 解决方案五: 中间三个div用浮动就行了 解决方案六: