网易Java工程师内推笔试交流
有人搞定第二个编程题吗，走迷宫那个。有弄明白的求解释一下，感觉个人理解题意有问题。#网易#
2016-08-02 22:09 西安电子科大 Java
关注
全部评论
明经
蚂蚁集团_高级开发工程师
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.LinkedBlockingQueue;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Queue<Integer> yqueue=new
LinkedBlockingQueue<>();
Queue<Integer> xqueue=new
LinkedBlockingQueue<>();
while (in.hasNext()) {
int n=in.nextInt();
int m=in.nextInt();
char[][] cs=new char[55][55];
bu[] bu=new bu[55];
in.nextLine();
for(int i=0;i<n;i++)
{
cs[i]=in.nextLine().toCharArray();
}
int x0=in.nextInt();
int y0=in.nextInt();
cs[x0][y0]='x';
int k=in.nextInt();
for(int i=0;i<k;i++)
{
int dx=in.nextInt();
int dy=in.nextInt();
bu[i]=new bu(dx, dy);
}
int[][] a=new int[55][55];
a[x0][y0]=0;
xqueue.add(x0);
yqueue.add(y0);
int x,y;
int max=-1;
while(!xqueue.isEmpty())
{
x=xqueue.poll();
y=yqueue.poll();
for(int i=0;i<k;i++)
{
// System.out.println(i);
if(x+bu[i].getDx()>=0&&y+bu[i].getDy()>=0&&
x+bu[i].getDx()<n&&y+bu[i].getDy()<m&&
a[x][y]+1>a[x+bu[i].getDx()][y+bu[i].getDy()]&&
cs[x+bu[i].getDx()][y+bu[i].getDy()]=='.')
{
a[x+bu[i].getDx()][y+bu[i].getDy()]=a[x][y]+1;
cs[x+bu[i].getDx()][y+bu[i].getDy()]='x';
xqueue.add(x+bu[i].getDx());
yqueue.add(y+bu[i].getDy());
if(a[x][y]+1>max)
{
max=a[x][y]+1;
}
//
System.out.print(x+bu[i].getDx());
//
System.out.println(y+bu[i].getDy());
}
}
}
int y1=0;
for(int x1=0,x2=n-1;y1<m;y1++)
{
if(a[x1][y1]!=0||a[x2][y1]!=0)
{
break;
}
}
if(y1==m)
{
max=-1;
}
System.out.println(max);
}
}
static class bu{
private int dx;
private int dy;
bu(){}
bu(int dx,int dy)
{
this.dx=dx;
this.dy=dy;
}
public int getDx() {
return dx;
}
public int getDy() {
return dy;
}
public void setDx(int dx) {
this.dx = dx;
}
public void setDy(int dy) {
this.dy = dy;
}
}
}
牛客2952189号
清华大学 Java
为什么一直头像上传失败，没有头像估计会死吧。
mebixus
中国科学院大学 安卓
我都没理解题意……
咔咔啦啦
山东科技大学 Java
我用的bfs 忘了求最大值了 结果就50%
wodeqiangne
浙江大学 Java
import java.util.*;
import java.util.*;
public class Main{
static int max = 0;
static byte[][] mat;
static int[][] dp;
static int k;
static int[] dx;
static int[] dy;
static int n;
static int m;
static boolean[][] craw;
static boolean flag = true;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
dp = new int[n][m];
scan.nextLine();
mat = new byte[n][m];
for(int i = 0; i < n; i++){
String tmp = scan.nextLine();
mat[i] = tmp.getBytes();
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
if((i == 0 || j== 0 || i == n-1 || j == m-1) && mat[i][j] == '.'){
dp[i][j] = Integer.MAX_VALUE;
}
}
craw = new boolean[n][m];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
craw[i][j] = false;
int startx = scan.nextInt();
int starty = scan.nextInt();
k = scan.nextInt();
dx = new int[k];
dy = new int[k];
for(int i = 0; i < k; i++){
dx[i] = scan.nextInt();
dy[i] = scan.nextInt();
}
craw[startx][starty] = true;
for(int i = 0; i < k; i++){
bfs(startx + dx[i], starty + dy[i], 0);
}
int result = -1;
for(int i = 0; i < n; i++){
if(dp[i][0] != Integer.MAX_VALUE)
result = Math.max(result, dp[i][0]);
}
for(int i = 0; i < m; i++){
if(dp[0][i] != Integer.MAX_VALUE)
result = Math.max(result, dp[0][i]);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)
System.out.print(dp[i][j] + " ");
System.out.println();
}
if(flag){System.out.println(-1);
}else{
System.out.println(result + 1);
}
}
private static void bfs(int x, int y,int len) {
// TODO Auto-generated method stub
if(x < 0 || x >= n || y < 0 || y > m)return;
if(mat[x][y] != '.' || craw[x][y])return;
craw[x][y] = true;
if((x == 0 || y == 0 || x == n-1 || y == m-1) && mat[x][y] == '.'){
flag = false;
int value = dp[x][y];
if(len < value){
dp[x][y] = len;
}
}
for(int i = 0; i < k; i++){
if(x + dx[i] < 0 || x + dx[i] >= n)continue;
if(y + dy[i] < 0 || y + dy[i] >= m)continue;
bfs(x + dx[i], y + dy[i], len+1);
}
craw[x][y] = false;
}
}
Cyif
浙江大学 Java
就是bfs啊，然后找出步数最多的
相关推荐
12-16 21:41
长沙理工大学 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享