问题描述
- 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