提高班第一次月测
2025-06-10 16:21:56
发布于：上海
42阅读
0回复
0点赞
T1
#include <iostream>
using namespace std;
const int N = 30;
char mp[N][N]; // 迷宫
int n, m, ans = 2e9; // 行，列，最短时间
int sx, sy, ex, ey; // (sx, sy) 起点，(ex, ey) 终点
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; // 方向数组
bool vis[N][N]; // 标记数组
bool in(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
// 搜索所有可能路径，并维护一个最短时间
void DFS(int x, int y, int sum) { // 正在访问 (x, y)，所花时间为 sum
if(x == ex && y == ey) { // 走到终点
if(sum < ans) ans = sum; // 更新最短时间
return; // 到达递归边界，返回
}
vis[x][y] = true;
for(int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 未越界 && 未访问 && 不是障碍物和墙
if(in(nx, ny) && !vis[nx][ny] && mp[nx][ny] != '#') {
if(mp[nx][ny] >= '1' && mp[nx][ny] <= '9')
DFS(nx, ny, sum + (mp[nx][ny] - '0') + 1); // 需要花费 1 分钟 + 消灭怪兽的时间
else
DFS(nx, ny, sum + 1); // 空地需要花费 1 分钟
}
}
vis[x][y] = false; // 回溯
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> mp[i][j];
if(mp[i][j] == 'Z') sx = i, sy = j; // 起点位置
if(mp[i][j] == 'W') ex = i, ey = j; // 终点位置
}
}
DFS(sx, sy, 0); // 从起点出发，找到到达终点的最短时间（也有可能找不到）
if(ans == 2e9) cout << "IMPOSSIBLE"; // 从起点无法到达终点
else cout << ans;
return 0;
}
T2
#include <iostream>
using namespace std;
const int N = 15;
int n, m, sx, sy, fx, fy, t, cnt;
int mp[N][N];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
bool vis[N][N]; //vis[x][y] 标记点(x,y)是否已访问
bool check(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x, int y){ // 当前位置 (x, y)
if(x == fx && y == fy){ // 边界：终点
cnt++; // 方案数加 1
return;
}
vis[x][y] = true; // 标记已经走过
for(int i = 0; i < 4; i++){
int nx = x + dir[i][0];
int ny = y + dir[i][1];
// 没有越界 && 没有访问 && 不是障碍物
if(check(nx,ny) && !vis[nx][ny] && mp[nx][ny] != 1){
dfs(nx, ny);
}
}
vis[x][y] = false; //回溯
}
int main() {
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
for(int i = 1; i <= t; i++){
int x, y;
cin >> x >> y;
mp[x][y] = 1;
}
dfs(sx,sy);
cout << cnt;
return 0;
}
T3
#include<bits/stdc++.h>
using namespace std;
char MAP[109][109];
bool vis[109][109];
int dir[8][2] = { -1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,-1,0 };//定义方向数组
int n, m;//定义n和m
bool inmap(int x, int y) {//定义函数inmap(x,y)判断(x,y)位置是否在地图内
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x, int y) {
vis[x][y] = 1;
for (int i = 0; i < 8; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if (inmap(nx, ny) && !vis[nx][ny] && MAP[nx][ny] == 'W') {//判断邻居是否在地图内并且没有被访问过并且不是障碍物
dfs(nx, ny);//调用dfs(nx,ny)，表示向该位置走
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> MAP[i] + 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!vis[i][j] && MAP[i][j] == 'W') {
ans++;
dfs(i, j);
}
}
}
cout << ans;
return 0;
}
T4
#include<bits/stdc++.h>
using namespace std;
char MAP[1509][1509];
int num[100009];
bool vis[1509][1509];
int dir[8][2] = { -1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1 };
int number, n, m; //number表示连通块大小
void dfs(int x, int y) { //递归求连通块大小
number++;
vis[x][y] = 1;
for (int i = 0; i < 8; i++) {
int xx = x + dir[i][0], yy = y + dir[i][1];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy] && MAP[xx][yy] == '*') dfs(xx, yy);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> MAP[i] + 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!vis[i][j] && MAP[i][j] == '*') {
number = 0;
dfs(i, j);
num[number]++;
}
}
}
int l = 0, r = 0;
for (int i = 1; i <= 100000; i++) {//枚举求答案
if (num[i])l++;
r = max(r, num[i] * i);
}
cout << l << " " << r;
return 0;
}
T5
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0;
int ans = 0;
char a[1510][1510]; // 用来存星空
int book[1510][1510]; // 用来标记那些星星我们已经找过他的星座了
int Stars[100010]; // 统计大小为i的星座有多少个
struct node {
int x, y; // BFS的结构体，所在第几行，第几列
} temp;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
// 方向数组，往八连通扩展
int bfs(int p0, int q0) { // 找到的这一颗星星的坐标是(p0,q0)
queue<node> q;
q.push({p0, q0});
book[p0][q0] = 1;
// 统计星座的大小
int Size_ = 0;
while (q.size()) {
Size_++; // 星座的大小加一
temp = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
int fx = temp.x + dx[i];
int fy = temp.y + dy[i];
// 下一个位置不越界，是星星，且不重复加入队列，并标记已经访问
if (fx >= 1 && fx <= n && fy >= 1 && fy <= m && a[fx][fy] == '*' && book[fx][fy] == 0) {
book[fx][fy] = 1;
q.push({fx, fy});
}
}
}
return Size_; // 返回星座大小
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
int w;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 如果是星星，并且没有找过他
if (a[i][j] == '*' && book[i][j] == 0) {
// 获取到星座大小,并且又多了一个大小是w的星座
w = bfs(i, j);
Stars[w]++;
}
}
}
for (int i = 1; i <= 100000; i++) {
// 如果存在大小是i的星座
if (Stars[i] != 0) {
// 那么他们可以组成一个星系，并且更新最大星系
cnt++;
ans = max(ans, (i * Stars[i]));
}
}
// 输出星系的数量与最大星系的大小
cout << cnt << " " << ans << endl;
return 0;
}
T6
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
bool prime[maxn];
int vis[maxn]; //vis[i]表示从Q到i需要的次数
void init() { //埃氏筛素数
prime[1] = 1;
for (int i = 2; i < maxn; i++) {
for (int j = 2 * i; j < maxn; j += i) prime[j] = 1;
}
}
int bfs(int Q, int W) {
memset(vis, -1, sizeof(vis)); //用-1表示从Q到不能到i，多组数据，每次需要初始化
queue<int> q;
q.push(Q);
vis[Q] = 0; //Q到Q的次数是0
while (q.size()) {
int r = q.front();
q.pop();
if (r == W) return vis[W];
for (int i = 0; i < 10; i++) {
//个位
int tm = r - r % 10 + i;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) { //题目说改变后的数要在1000~9999范围内
q.push(tm);
vis[tm] = vis[r] + 1;
}
//十位
tm = r - (r / 10 % 10) * 10 + i * 10;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) {
q.push(tm);
vis[tm] = vis[r] + 1;
}
//百位
tm = r - (r / 100 % 10) * 100 + i * 100;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) {
q.push(tm);
vis[tm] = vis[r] + 1;
}
//千位
tm = r - (r / 1000 % 10) * 1000 + i * 1000;
if (prime[tm] == 0 && vis[tm] == -1 && tm >= 1000) {
q.push(tm);
vis[tm] = vis[r] + 1;
}
}
}
return 0;
}
int main() {
init();
int _;
cin >> _;
while (_--) {
int Q, W;
cin >> Q >> W;
cout << bfs(Q, W) << '\n';
}
return 0;
}
有帮助，赞一个