哪个网站做logo设计师,个人怎样申请网站,网站建设 物流,怎么在建设银行网站留言《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
造…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
造电梯” 链接
http://oj.ecustacm.cn/problem.php?id1790 题目描述
【题目描述】 现在给你一张建筑的平面图按照要求建筑的每一个部分都应该是轮椅使用者可以到达的这意味着必须安装电梯。 给定的平面图是一个n*m的矩阵里面的数字表示这个位置的高度。可以在建筑中的任意位置放置电梯电梯可以停在所有楼层。 需要保证可以使用电梯到达所有高楼层。相同高度的楼层之间是互通的联通准则是四联通。 需要求解最少需要多少个电梯注意高度为1的不需要电梯。 下图展示了样例2的可视化三维图。
【输入格式】 输入第一行为n和m(1≤n,m≤500)。 接下来n行每行m个整数xij表示平面图0≤xij≤10^9。 【输出格式】 输出最少电梯数量 【输入样例】
样例1
2 3
1 2 3
1 3 2样例2
6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0【输出样例】
样例1
2样例2
2题解 电梯是装在建筑内部的例如样例2高度5的柱子内部需要一个电梯楼梯状的建筑也需要一个电梯。 注意一个建筑内部可能需要不止一个电梯例如平面上一个建筑的高度是{5, 2, 4}那么需要在5和4上建2个电梯。 本题是“洪水填充《算法竞赛》清华大学出版社罗勇军郭卫斌著120页3.3 洪水填充”的应用从最高处开始倒水那么水会平流或者往下流这相当于建了一部电梯这次倒水没有流到的地方继续从下一个最高处倒水… 以样例2为例 1从最高的“5”开始倒水水会平流或往下流那么会继续淹没所有的“0”。这次倒水相当于建设了一部电梯。没有被这次倒水淹没的有第二行和第三行的“1 2 3 2 1”还有倒数第二行的“1”。 2继续从剩下的最高点“3”开始倒水水会平流或往下流那么第二行和第三行的“1 2 3 2 1”还有所有的“0”都会淹没。这次倒水也相当于建设了一部电梯。没有被这次倒水淹没的有倒数第二行的“1”不过它不需要建设电梯。 “洪水填充”用BFS或DFS都行下面的代码用BFS实现。把平面的所有点放进优先队列然后依次取出队列中的最高点并从它开始“洪水填充”。 【重点】 洪水填充。
C代码 代码的计算复杂度设平面上共n个点每个点只需要处理一次优先队列进出一次是O(logn)的所以总复杂度O(nlogn)。
#include bits/stdc.h
using namespace std;
int dx[4] { 1, 0, -1, 0 }; //上下左右
int dy[4] { 0, 1, 0, -1 };
struct Point {int x, y, h; //坐标xy、高度hPoint(int x_, int y_, int h_) { x x_; y y_; h h_; };bool operator(const Point r) const { return (h r.h); }
};
int n, m;
int a[505][505];
bool done[505][505]; //done[x][y]1表示(x,y)已经淹没
void floodfill(int x, int y) { //“洪水填充”平流或往下流done[x][y] true; //标记为淹没for (int i 0; i 4; i) { //扩散周围与它等高或矮的点int nx x dx[i], ny y dy[i];if (nx 0 || nx m || ny 0 || ny n || done[nx][ny]) continue;if (a[nx][ny] a[x][y])floodfill(nx, ny); //继续“洪水填充”}
}
int main() {cin n m;priority_queuePoint Q; //优先队列队首的h最大for (int j 0; j n; j)for (int i 0; i m; i) {cin a[i][j];done[i][j] (a[i][j] 1); //0和1标记为已经淹没if(a[i][j] 1)Q.push(Point(i, j, a[i][j])); //把点放进优先队列}int ans 0;while (!Q.empty()) {Point p Q.top(); //每次取出剩下的最高点Q.pop();if (!done[p.x][p.y]) { //如果它没有淹没过就“洪水填充”ans; //这次倒水相当于建设了一部电梯floodfill(p.x, p.y); //“洪水填充”}}cout ans endl;return 0;
}
Java代码
import java.util.*;
class Point implements ComparablePoint {int x, y, h;public Point(int x_, int y_, int h_) {x x_;y y_;h h_;}public int compareTo(Point r) { return Integer.compare(-h, -r.h); }
}public class Main {static int[] dx { 1, 0, -1, 0 };static int[] dy { 0, 1, 0, -1 };static int n, m;static int[][] a;static boolean[][] done;public static void floodfill(int x, int y) {done[x][y] true;for (int i 0; i 4; i) {int nx x dx[i], ny y dy[i];if (nx 0 || nx m || ny 0 || ny n || done[nx][ny])continue;if (a[nx][ny] a[x][y])floodfill(nx, ny);}}public static void floodfill_bfs(int sx, int sy) {Queueint[] queue new LinkedList();queue.add(new int[] { sx, sy });done[sx][sy] true;while (!queue.isEmpty()) {int[] curr queue.poll();int x curr[0];int y curr[1];for (int i 0; i 4; i) {int nx x dx[i], ny y dy[i];if (nx 0 nx m ny 0 ny n !done[nx][ny] a[nx][ny] a[x][y]) {queue.add(new int[] { nx, ny });done[nx][ny] true;}}}}public static void main(String[] args) {Scanner input new Scanner(System.in);n input.nextInt();m input.nextInt();a new int[m][n];done new boolean[m][n];PriorityQueuePoint Q new PriorityQueue();for (int j 0; j n; j) {for (int i 0; i m; i) {a[i][j] input.nextInt();done[i][j] (a[i][j] 1);if (a[i][j] 1) Q.add(new Point(i, j, a[i][j]));}}int ans 0;while (!Q.isEmpty()) {Point p Q.poll();if (!done[p.x][p.y]) {ans;floodfill_bfs(p.x, p.y);}}System.out.println(ans);input.close();}
}Python代码
from collections import deque
import heapq
import sys
input sys.stdin.readlinedx [1, 0, -1, 0]
dy [0, 1, 0, -1]
n, m map(int, input().split())
a [[0] * n for _ in range(m)]
done [[False] * n for _ in range(m)]Q []
for j in range(n):row_a list(map(int, input().split()))for i in range(m):a[i][j] row_a[i]if a[i][j] 1: done[i][j]Trueelse: heapq.heappush(Q, (-a[i][j], i, j))
ans 0
while Q:_, sx, sy heapq.heappop(Q)if not done[sx][sy]:ans 1q deque([(sx, sy)])done[sx][sy] True while q:x, y q.popleft()for i in range(4):nx, ny x dx[i], y dy[i]if 0 nx m and 0 ny n and not done[nx][ny] and a[nx][ny] a[x][y]:q.append((nx, ny))done[nx][ny] True
print(ans)
文章转载自： http://www.morning.gsksm.cn.gov.cn.gsksm.cn http://www.morning.zbqry.cn.gov.cn.zbqry.cn http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.mjglk.cn.gov.cn.mjglk.cn http://www.morning.jzgxp.cn.gov.cn.jzgxp.cn http://www.morning.rzscb.cn.gov.cn.rzscb.cn http://www.morning.zdhxm.com.gov.cn.zdhxm.com http://www.morning.lfcnj.cn.gov.cn.lfcnj.cn http://www.morning.mbmtz.cn.gov.cn.mbmtz.cn http://www.morning.rdng.cn.gov.cn.rdng.cn http://www.morning.ykmkz.cn.gov.cn.ykmkz.cn http://www.morning.hjlwt.cn.gov.cn.hjlwt.cn http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn http://www.morning.lsssx.cn.gov.cn.lsssx.cn http://www.morning.nlkm.cn.gov.cn.nlkm.cn http://www.morning.ynlpy.cn.gov.cn.ynlpy.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.hhskr.cn.gov.cn.hhskr.cn http://www.morning.zqnmp.cn.gov.cn.zqnmp.cn http://www.morning.mxbks.cn.gov.cn.mxbks.cn http://www.morning.fwkjp.cn.gov.cn.fwkjp.cn http://www.morning.qbjrf.cn.gov.cn.qbjrf.cn http://www.morning.sskkf.cn.gov.cn.sskkf.cn http://www.morning.mxtjl.cn.gov.cn.mxtjl.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.klyyd.cn.gov.cn.klyyd.cn http://www.morning.jtdrz.cn.gov.cn.jtdrz.cn http://www.morning.gjlxn.cn.gov.cn.gjlxn.cn http://www.morning.wrdpj.cn.gov.cn.wrdpj.cn http://www.morning.nkhdt.cn.gov.cn.nkhdt.cn http://www.morning.cyyhy.cn.gov.cn.cyyhy.cn http://www.morning.pbsqr.cn.gov.cn.pbsqr.cn http://www.morning.nrgdc.cn.gov.cn.nrgdc.cn http://www.morning.dmtbs.cn.gov.cn.dmtbs.cn http://www.morning.gnfkl.cn.gov.cn.gnfkl.cn http://www.morning.jqbpn.cn.gov.cn.jqbpn.cn http://www.morning.xyyplp.cn.gov.cn.xyyplp.cn http://www.morning.bpmft.cn.gov.cn.bpmft.cn http://www.morning.dpgdj.cn.gov.cn.dpgdj.cn http://www.morning.cbnjt.cn.gov.cn.cbnjt.cn http://www.morning.bpxmw.cn.gov.cn.bpxmw.cn http://www.morning.tzmjc.cn.gov.cn.tzmjc.cn http://www.morning.rxlk.cn.gov.cn.rxlk.cn http://www.morning.stprd.cn.gov.cn.stprd.cn http://www.morning.jjmrx.cn.gov.cn.jjmrx.cn http://www.morning.bkjhx.cn.gov.cn.bkjhx.cn http://www.morning.jbpodhb.cn.gov.cn.jbpodhb.cn http://www.morning.jpmcb.cn.gov.cn.jpmcb.cn http://www.morning.gtwtk.cn.gov.cn.gtwtk.cn http://www.morning.hrhwn.cn.gov.cn.hrhwn.cn http://www.morning.8yitong.com.gov.cn.8yitong.com http://www.morning.ndpzm.cn.gov.cn.ndpzm.cn http://www.morning.rfbpq.cn.gov.cn.rfbpq.cn http://www.morning.sjsks.cn.gov.cn.sjsks.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.pmsl.cn.gov.cn.pmsl.cn http://www.morning.vvbsxm.cn.gov.cn.vvbsxm.cn http://www.morning.stph.cn.gov.cn.stph.cn http://www.morning.mbmtz.cn.gov.cn.mbmtz.cn http://www.morning.kyzxh.cn.gov.cn.kyzxh.cn http://www.morning.qpljg.cn.gov.cn.qpljg.cn http://www.morning.knscf.cn.gov.cn.knscf.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.qqtzn.cn.gov.cn.qqtzn.cn http://www.morning.ychrn.cn.gov.cn.ychrn.cn http://www.morning.nrydm.cn.gov.cn.nrydm.cn http://www.morning.dmzzt.cn.gov.cn.dmzzt.cn http://www.morning.rgtp.cn.gov.cn.rgtp.cn http://www.morning.ryxdf.cn.gov.cn.ryxdf.cn http://www.morning.rfzzw.com.gov.cn.rfzzw.com http://www.morning.rnqrl.cn.gov.cn.rnqrl.cn http://www.morning.klcdt.cn.gov.cn.klcdt.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.mqwnz.cn.gov.cn.mqwnz.cn http://www.morning.nrbcx.cn.gov.cn.nrbcx.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.xnqjs.cn.gov.cn.xnqjs.cn http://www.morning.rlpmy.cn.gov.cn.rlpmy.cn http://www.morning.ndxss.cn.gov.cn.ndxss.cn
