备战蓝桥之搜索

2024.3.12

P2802 回家 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


 

import java.awt.Checkbox;
import java.awt.PageAttributes.OriginType;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;

import javax.print.attribute.standard.JobMessageFromOperator;
public class Main {	
  public static void main(String[] args) throws NumberFormatException, IOException  {
	  Scanner scanner=new Scanner(System.in);
	 BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
	 PrintWriter pw1=new PrintWriter(System.out);
     String[] aStrings=br1.readLine().split(" ");
aa=Integer.parseInt(aStrings[0]);
bb=Integer.parseInt(aStrings[1]);
cc=new int[aa][bb];
visited=new int[aa][bb];
int a,b;
for(a=0;a<aa;a++) {
	String[] bStrings=br1.readLine().split(" ");
	for(b=0;b<bb;b++) {
		cc[a][b]=Integer.parseInt(bStrings[b]);
	}
}
for(a=0;a<aa;a++) {
	for(b=0;b<bb;b++) {
		if(cc[a][b]==2) {
			startx=a;
			starty=b;
		}
		if(cc[a][b]==3) {
			
			endx=a;
			endy=b;
			
		}
	}
}
ll1.add(new dian(startx, starty, 6, 0));
visited[startx][starty]=6;
while(ll1.size()!=0) {
	dian c1=ll1.remove();
	int x=c1.x;
	int y=c1.y;
	if(x==endx&&y==endy) {
		
		System.out.println(c1.juli);
		return;
	}
	int d;
	int juli=c1.juli;
	int blue=c1.blou;
	for(d=0;d<4;d++) {
		int x1=x+xx[d];
		int y1=y+yy[d];
		int blue2=blue;
		if(x1>=0&&x1<aa&&y1>=0&&y1<bb&&blue2>1&&(cc[x1][y1]==4||cc[x1][y1]==1||cc[x1][y1]==3)) {
			blue2=blue2-1;
			if(visited[x1][y1]<blue2) {
				
				if(cc[x1][y1]==4) {
					blue2=6;
				}
				
				visited[x1][y1]=blue2;
				ll1.add(new dian(x1, y1, blue2, juli+1));
			}
		}
	}
}
System.out.println("-1");
	}
	public static int aa,bb;
	public static int startx,starty;
	public static int endx,endy;
	public static int[][] visited;
	public static int[][] cc;
	public static int[] xx= {-1,1,0,0};
	public static int[] yy= {0,0,-1,1};
	public static LinkedList<dian> ll1=new LinkedList<>();
	}
class dian{
	int x;
	int y;
	int blou;
	int juli;
	public dian(int x, int y, int blou, int juli) {
		super();
		this.x = x;
		this.y = y;
		this.blou = blou;
		this.juli = juli;
	}
	
}

package qq;

import java.awt.Checkbox;
import java.awt.PageAttributes.OriginType;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class main {	
  public static void main(String[] args) throws NumberFormatException, IOException  {
	  Scanner scanner=new Scanner(System.in);
	 BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));
	 PrintWriter pw1=new PrintWriter(System.out);
     String[] aStrings=br1.readLine().split(" ");
 bb=Integer.parseInt(aStrings[0]);
 cc=Integer.parseInt(aStrings[1]);
 visited=new int[bb][cc];
 aa=new char[bb][cc];
 int a,b;
 for(a=0;a<bb;a++) {
	aa[a]=br1.readLine().toCharArray();
 }
 for(a=0;a<bb;a++) {
	 for(b=0;b<cc;b++) {
		if(aa[a][b]=='s') {
			startx=a;
			starty=b;
		}
		if(aa[a][b]=='g') {
			endx=a;
			endy=b;
		}
	 }
 }
 ll1.add(new dian(startx, starty));
 visited[startx][starty]=1;
 while(ll1.size()!=0) {
	 dian c1=ll1.remove();
	 int x=c1.x;
	 int y=c1.y;
	 int d;
	 if(x==endx&&y==endy) {
		 System.out.println("Yes");
		 return;
	 }
	 for(d=0;d<4;d++) {
		 int x1=x+xx[d];
		 int y1=y+yy[d];
	
		 if(x1>=0&&x1<bb&&y1>=0&&y1<cc&&visited[x1][y1]==0&&(aa[x1][y1]=='.'||aa[x1][y1]=='g')) {
			 
			 visited[x1][y1]=1;
			 ll1.add(new dian(x1, y1));
		 }
	 }
 }
 System.out.println("No");
  }
public static LinkedList<dian> ll1=new LinkedList<>();
public static int[][] visited;
public static char[][] aa;
public static int[] xx= {-1,1,0,0};
public static int[] yy= {0,0,-1,1};
public static int bb,cc;
public static int startx,starty;
public static int endx,endy;
}
class dian{
	int x;
	int y;
	public dian(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}