import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Main { static int n,m; static int x1,y1,x2,y2; static final int[] dx={1,0,-1,0}; static final int[] dy={0,1,0,-1}; static String[] map; static boolean[][] vis1; static boolean[][] vis2; static int[][] time1; static int[][] time2; static final int inf=99999999; public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ n=sc.nextInt(); m=sc.nextInt(); map=new String[n]; vis1=new boolean[n][m]; vis2=new boolean[n][m]; time1=new int[n][m]; time2=new int[n][m]; for (int i = 0; i < n; i++) { map[i]=sc.next(); for (int j = 0; j < m; j++) { if(map[i].charAt(j)==‘Y‘){ x1=i; y1=j; } if(map[i].charAt(j)==‘M‘){ x2=i; y2=j; } } } ArrayList<Block> a1=new ArrayList<>(); ArrayList<Block> a2=new ArrayList<>(); LinkedList<Block> q=new LinkedList<Block>(); q.addLast(new Block(x1,y1,0)); vis1[x1][y1]=true; LinkedList<Block> p=new LinkedList<Block>(); p.addLast(new Block(x2,y2,0)); vis2[x2][y2]=true; int t1=inf,t2=inf; int t=inf; int flag=0; // while(true){ // int s1=q.size(); // int s2=p.size(); while(!q.isEmpty()) { Block b=q.removeFirst(); if(map[b.x].charAt(b.y)==‘@‘){ // a1.add(b); // for (int i = 0; i < a2.size(); i++) { // if(a2.get(i).x==b.x&&a2.get(i).y==b.y){ // t1=a2.get(i).t+b.t; // break; // } // } // break; } for (int i = 0; i < 4; i++) { int xx=b.x+dx[i]; int yy=b.y+dy[i]; if(check(xx,yy)&&!vis1[xx][yy]){ vis1[xx][yy]=true; q.addLast(new Block(xx,yy,b.t+1)); time1[xx][yy]=b.t+1; } } } while(!p.isEmpty()) { Block b=p.removeFirst(); if(map[b.x].charAt(b.y)==‘@‘){ time2[b.x][b.y]=b.t; // a2.add(b); // for (int i = 0; i < a1.size(); i++) { // if(a1.get(i).x==b.x&&a1.get(i).y==b.y){ // t2=a1.get(i).t+b.t; // break; // } // } // break; } for (int i = 0; i < 4; i++) { int xx=b.x+dx[i]; int yy=b.y+dy[i]; if(check(xx,yy)&&!vis2[xx][yy]){ vis2[xx][yy]=true; p.addLast(new Block(xx,yy,b.t+1)); time2[xx][yy]=b.t+1; } } } // for (int i = 0; i < a1.size(); i++) { // for (int j = 0; j < a2.size(); j++) { // if(a1.get(i).x==a2.get(j).x&&a1.get(i).y==a2.get(j).y){ // t=a1.get(i).t+a2.get(j).t; // flag=1; // } // } // } // if(flag==1){ // break; // } // if(a1.size()==1&&a2.size()==1){ // if(t1!=inf||t2!=inf){ // t=min(t1,t2); // break; // } // } // if(t1!=inf&&t2!=inf){ // t=min(t1,t2); // break; // } // } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if(map[i].charAt(j)==‘@‘&&time1[i][j]!=0&&time2[i][j]!=0){ if(t>time1[i][j]+time2[i][j]){ t=time1[i][j]+time2[i][j]; } } } } System.out.println(t*11); } } private static int min(int t1, int t2) { if(t1>t2) return t2; return t1; } private static boolean check(int x,int y) { if(x>=0&&y>=0&&x<n&&y<m&&map[x].charAt(y)!=‘#‘) return true; return false; } public static class Block{ int x; int y; int t; public Block(int x, int y, int t) { this.x = x; this.y = y; this.t = t; } } }
将地图上所有KFC都遍历一遍算出时间，最后输出和最小的
import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Main { static int n,m; static int x1,y1,x2,y2; static final int[] dx={1,0,-1,0}; static final int[] dy={0,1,0,-1}; static String[] map; static boolean[][] vis1; static boolean[][] vis2; static int[][] time1; static int[][] time2; static final int inf=99999999; public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ n=sc.nextInt(); m=sc.nextInt(); map=new String[n]; vis1=new boolean[n][m]; vis2=new boolean[n][m]; time1=new int[n][m]; time2=new int[n][m]; for (int i = 0; i < n; i++) { map[i]=sc.next(); for (int j = 0; j < m; j++) { if(map[i].charAt(j)==‘Y‘){ x1=i; y1=j; } if(map[i].charAt(j)==‘M‘){ x2=i; y2=j; } } } ArrayList<Block> a1=new ArrayList<>(); ArrayList<Block> a2=new ArrayList<>(); LinkedList<Block> q=new LinkedList<Block>(); q.addLast(new Block(x1,y1,0)); vis1[x1][y1]=true; LinkedList<Block> p=new LinkedList<Block>(); p.addLast(new Block(x2,y2,0)); vis2[x2][y2]=true; int t1=inf,t2=inf; int t=inf; int flag=0; while(true) { int s1 = q.size(); int s2 = p.size(); for (int j = 0; j < s1; j++) { Block b = q.removeFirst(); if (map[b.x].charAt(b.y) == ‘@‘) { time1[b.x][b.y] = b.t; // a1.add(b); // for (int i = 0; i < a2.size(); i++) { // if(a2.get(i).x==b.x&&a2.get(i).y==b.y){ // t1=a2.get(i).t+b.t; // break; // } // } // break; } for (int i = 0; i < 4; i++) { int xx = b.x + dx[i]; int yy = b.y + dy[i]; if (check(xx, yy) && !vis1[xx][yy]) { vis1[xx][yy] = true; q.addLast(new Block(xx, yy, b.t + 1)); } } } for (int j = 0; j < s2; j++) { Block b = p.removeFirst(); if (map[b.x].charAt(b.y) == ‘@‘) { time2[b.x][b.y] = b.t; // a2.add(b); // for (int i = 0; i < a1.size(); i++) { // if(a1.get(i).x==b.x&&a1.get(i).y==b.y){ // t2=a1.get(i).t+b.t; // break; // } // } // break; } for (int i = 0; i < 4; i++) { int xx = b.x + dx[i]; int yy = b.y + dy[i]; if (check(xx, yy) && !vis2[xx][yy]) { vis2[xx][yy] = true; p.addLast(new Block(xx, yy, b.t + 1)); } } } // for (int i = 0; i < a1.size(); i++) { // for (int j = 0; j < a2.size(); j++) { // if(a1.get(i).x==a2.get(j).x&&a1.get(i).y==a2.get(j).y){ // t=a1.get(i).t+a2.get(j).t; // flag=1; // } // } // } // if(flag==1){ // break; // } // if(a1.size()==1&&a2.size()==1){ // if(t1!=inf||t2!=inf){ // t=min(t1,t2); // break; // } // } // if(t1!=inf&&t2!=inf){ // t=min(t1,t2); // break; // } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (time1[i][j] != 0 && time2[i][j] != 0) { t = time1[i][j] + time2[i][j]; flag=1; } } } if(flag==1){ System.out.println(t * 11); break; } } } } private static int min(int t1, int t2) { if(t1>t2) return t2; return t1; } private static boolean check(int x,int y) { if(x>=0&&y>=0&&x<n&&y<m&&map[x].charAt(y)!=‘#‘) return true; return false; } public static class Block{ int x; int y; int t; public Block(int x, int y, int t) { this.x = x; this.y = y; this.t = t; } } }
这个是每走一步看一下有没有经过相同的KFC。这个想法样本能过但测试过不去
原文：https://www.cnblogs.com/lijiahui-123/p/13285018.html