前言
提示:这里可以添加本文要记录的大概内容:
例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。
提示:以下是本篇文章正文内容,下面案例可供参考
一、``173. 矩阵距离(acwing)
import java.io.*; import java.util.*; public class Main { static int N=1010; static int n,m; static char[][] a=new char[N][N]; static int[][] b=new int[N][N]; static Queue<int[]> queue=new LinkedList<>(); static boolean[][] st=new boolean[N][N]; static int[] dx={1,-1,0,0}; static int[] dy={0,0,1,-1}; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer sth = new StreamTokenizer(br); static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); public static void main(String[] args) throws Exception { n=nextInt(); m=nextInt(); for (int i = 0; i <n; i++) { a[i]=br.readLine().toCharArray(); for (int j = 0; j <m; j++) { if (a[i][j]=='1'){ st[i][j]=true; queue.offer(new int[]{i,j}); } } } int tmp=0; while (!queue.isEmpty()){ int size=queue.size(); while (size-->0){ int[] curr=queue.poll(); int x=curr[0]; int y=curr[1]; b[x][y]=tmp; for (int i = 0; i < 4; i++) { int newX=x+dx[i]; int newY=y+dy[i]; if (newX>=0&&newX<n&&newY>=0&&newY<m&&!st[newX][newY]){ queue.offer(new int[]{newX,newY}); st[newX][newY]=true; } } } tmp++; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { out.print(b[i][j]+" "); } out.println(); } out.flush(); } // 读入整形(一个) public static int nextInt() throws Exception { sth.nextToken(); return (int) sth.nval; // nval 读入的是 double 类型 } }
二、5475 聚会
#include <bits/stdc++.h> using namespace std; const int N = 100010, M = 2 * N; int n, m, k, s; int dist[N][101]; int h[N], e[M], ne[M], idx; int q[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void bfs(vector<int> &begin, int c) { int hh = 0, tt = -1; for(int i = 1;i <= n; ++ i) dist[i][c] = 1e9; for(auto it: begin) { q[ ++ tt] = it; dist[it][c] = 0; } while(hh <= tt) { auto u = q[hh ++ ]; for(int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(dist[j][c] > dist[u][c] + 1) { dist[j][c] = dist[u][c] + 1; q[ ++ tt] = j; } } } } void work(int u) { static int tmp[101]; int cnt = 0; for(int i = 1;i <= k; ++ i) tmp[i] = dist[u][i]; sort(tmp + 1, tmp + k + 1); int res = 0; for(int i = 1;i <= s; ++ i) res += tmp[i]; printf("%d ", res); } int main() { cin >> n >> m >> k >> s; memset(h, -1, sizeof h); vector<int> a(n + 1); vector<vector<int>> color(k + 1); for(int i = 1;i <= n; ++ i) { scanf("%d", &a[i]); color[a[i]].push_back(i); } while(m -- ) { int u, v; scanf("%d%d", &u, &v); add(u, v), add(v, u); } for(int i = 1;i <= k; ++ i) { bfs(color[i], i); } for(int i = 1;i <= n; ++ i) work(i); return 0; }