网易互娱4.11三道笔试题求思路/指正
输入
2
10 3
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 2 0 0 0
0 0 0 0 0 0 0 0 0 2
0 0 0 1 0 0 0 0 0 1
0 0 0 1 0 0 2 0 2 0
8 8
10 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 1 0 0 0 0
0 0 0 1 2 0 2 0 0 0
0 0 0 0 2 1 2 0 2 0
0 0 2 0 0 0 0 0 2 0
0 0 0 0 0 0 0 2 0 0
0 0 0 1 0 0 0 0 0 0
2 5
输出
17
做法: BFS
import java.util.*;
public class Main{
static int[][] directions = new int[][] {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int num = in.nextInt();
//in.nextLine();
//System.out.println("");
for(int t=0; t<num; t++){
int m=in.nextInt();
int len=in.nextInt();
int[][] grid=new int[m][m];
in.nextLine();
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
grid[i][j]=in.nextInt();
}
}
int x=in.nextInt();
int y=in.nextInt();
boolean[][] visited = new boolean[m][m];
System.out.println(lenOfBlade(grid, len, visited, x, y));
//in.nextLine();
}
}
public static int lenOfBlade(int[][] grid, int len, boolean[][] visited, int i, int j){
if(grid==null || grid.length==0 || grid[0].length==0)
return len;
int m=grid.length;
Queue<int[]> q= new LinkedList<>();
q.offer(new int[]{i, j});
while(!q.isEmpty()){
int size=q.size();
int plus=0;
for(int n=0; n<size; n++){
int[] cur=q.poll();
int x=cur[0];
int y=cur[1];
//System.out.println("x: "+x+", y: "+y);
visited[x][y]=true;
plus+=grid[x][y];
grid[x][y]=0;
for(int[] d: directions){
int xx=x+d[0];
int yy=y+d[1];
if(xx<0 || xx>=m || yy<0 || yy>=m || ((xx-i)*(xx-i)+(yy-j)*(yy-j)>len*len)|| visited[xx][yy]==true){
continue;
}
q.offer(new int[]{xx,yy});
}
}
len+=plus;
}
return len;
}
}
2.不嗨会
输入:
3
3 7
3 1
1 1 2
3 1
1 2 3
3 1
2 1
3 1
3 5
1 2 3
3 1
2 3
1 2 1
3 1
3 5
1 2 3
1 2 1
3 1
2 3
3 1
输出:
1
2
3
1
1
2
3
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int T = in.nextInt(); for(int i=0; i<T; i++){ int n=in.nextInt(); int m=in.nextInt(); System.out.println("老子不会"); } } }
输入
3
3
1 2 3
1 2 3
4
4 3 2 1
1 1 1 1
2
1 2
10 20
输出
7
4
30
import java.util.*; public class Test{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int T = in.nextInt(); for(int t=0; t<T; t++){ int n=in.nextInt(); int[] A=new int[n]; //int[] B=new int[n]; int[] V=new int[n]; for(int i=0; i<n; i++){ A[i]=in.nextInt(); } for(int i=0; i<n; i++){ V[i]=in.nextInt(); } System.out.println(minDistance(n,A,V)); } } public static int minDistance(int n, int[] A, int[] D){ if(A==null || A.length==0 || A.length!=D.length) return 0; int[][] dp=new int[n][n]; //i j 分别代表i-j匹配 PriorityQueue<int[]>[] pq_list = new PriorityQueue[n]; for(int i=0; i<n; i++){ pq_list[i]=new PriorityQueue<int[]>(new Comparator<int []>(){ public int compare(int[] a, int[] b){ return a[1]-b[1]; } }); for(int j=0; j<n; j++){ if(i==j) continue; //dp[i][j]=V[i]*Math.abs(i-j); pq_list[i].offer(new int[]{j,D[i]*Math.abs(i-j)}); } } int sum=0; boolean[] visited=new boolean[n]; PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b)->D[b]-D[a]); for(int i=0; i<n; i++){ pq.offer(i); } while(!pq.isEmpty()){ int cur=pq.poll(); //System.out.println(cur); PriorityQueue<int[]> sub_pq=pq_list[cur]; while(!sub_pq.isEmpty()){ int[] pair=sub_pq.poll(); int pos=pair[0]; int val=pair[1]; if(visited[pos]==true) continue; sum+=val; visited[pos]=true; break; } } return sum; } }