俞天行
(ytxqwq)
1
《Dan的小香脚》
题目背景：
Dan具有有史以来最香的香脚，他的jio能释放出巨大的毒气
题目描述：
Dan的体委ZCJ把他们搞得没法干饭，于是，他决定报复社会！他们的学校是一个迷宫，他脱下鞋子，让脚气扩散。jio气会从一个区域扩散到相邻的区域（上下左右）。迷宫用一个二维方格表示，其中‘0’表示可以通行的区域，‘1’表示墙壁，无法穿过。感染会从有香脚的格子传播到四个相邻的格子（上下左右）。如果一个格子被感染，则在下一个步骤之前，它将成为“感染”的状态。你的任务是模拟这一过程，并确定在给定步数后哪些格子会被感染。
输入格式：
- 第一行输入两个整数
n 和 m，表示迷宫的行数和列数（1 ≤ n, m ≤ 100）。
- 接下来的
n 行中，每行包含 m 个字符：‘0’表示可以通行（无香脚），‘1’表示墙壁（有香脚），‘2’表示初始感染（香脚格子）。
- 最后一行输入一个整数
k，表示步数（1 ≤ k ≤ 10）。
输出格式：
输出经过 k 步后，迷宫上每个格子的状态，用字符表示：‘0’（无香脚），‘1’（墙壁），‘2’（感染）为输出的状态，以行的形式输出。
示例
输入示例：
4 5
0 1 0 0 2
0 1 0 1 0
0 0 0 1 0
1 1 0 0 0
2
输出示例：
0 1 2 2 2
0 1 0 1 2
0 0 0 1 2
1 1 0 0 0
谁来帮助大家，解决香脚？
4 个赞
楼逸杨
(楼逸杨)
10
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 105;
const int MAXM = 105;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct node {
int x, y;
};
void bfs(int n, int m, int mapn[MAXN][MAXM], int k) {
// 使用队列来记录需要处理的感染格子
queue<node> qu;
// 初始化队列，将初始感染的格子加入队列
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mapn[i][j] == 2) { // 状态2代表初始感染
qu.push({i, j});
}
}
}
// 进行k步模拟感染扩散
for (int j = 0; j < k; j++) {
int size = qu.size();
for (int k = 0; k < size; k++) {
node now = qu.front();
qu.pop();
// 扩散到上下左右四个方向
for (int i = 0; i < 4; i++) {
int now_x = now.x + dx[i];
int now_y = now.y + dy[i];
// 检查合法性和是否可感染
if (now_x >= 0 && now_x < n &&
now_y >= 0 && now_y < m &&
mapn[now_x][now_y] == 0) {
mapn[now_x][now_y] = 2; // 将其感染
qu.push({now_x, now_y}); // 加入队列以便后续处理
}
}
}
}
}
int main(void)
{
int n, m; // 行数和列数
cin >> n >> m;
int mapn[MAXN][MAXM]; // 迷宫状态
// 输入迷宫状态
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '0') {
mapn[i][j] = 0; // 无香脚格子
} else if (c == '1') {
mapn[i][j] = 1; // 墙壁
} else if (c == '2') {
mapn[i][j] = 2; // 初始感染格子
}
}
}
int k; // 步数
cin >> k;
// 进行感染扩散模拟
bfs(n, m, mapn, k);
// 输出最终状态
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mapn[i][j] == 0) {
cout << '0';
} else if (mapn[i][j] == 1) {
cout << '1';
} else if (mapn[i][j] == 2) {
cout << '2';
}
if (j < m - 1) cout << ' ';
}
cout << endl;
}
return 0;
}
1 个赞
汪嘉乐
(汪嘉乐)
17
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 105;
const int MAXM = 105;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct node {
int x, y;
};
void dfs(int x, int y, int step, int n, int m, int mapn[MAXN][MAXM], int k) {
if(step>=k)return;
for (int i = 0; i < 4; i++) {
int now_x = x + dx[i];
int now_y = y + dy[i];
if (now_x >= 0 && now_x < n && now_y >= 0 && now_y < m && mapn[now_x][now_y] == 0) {
mapn[now_x][now_y] = 2;
dfs(now_x,now_y,step+1,n,m,mapn,k);
}
}
}
int main(void)
{
int n, m; // 行数和列数
cin >> n >> m;
int mapn[MAXN][MAXM]; // 迷宫状态
// 输入迷宫状态
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '0') {
mapn[i][j] = 0; // 无香脚格子
} else if (c == '1') {
mapn[i][j] = 1; // 墙壁
} else if (c == '2') {
mapn[i][j] = 2; // 初始感染格子
}
}
}
int k; // 步数
cin >> k;
// 进行感染扩散模拟
vector<int>mbx;
vector<int>mby;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(mapn[i][j]==2){
mbx.push_back(i);
mby.push_back(j);
}
}
}
for(int i=0;i<mbx.size();i++)
dfs(mbx[i],mby[i],0,n, m, mapn, k);
// 输出最终状态
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mapn[i][j] == 0) {
cout << '0';
} else if (mapn[i][j] == 1) {
cout << '1';
} else if (mapn[i][j] == 2) {
cout << '2';
}
if (j < m - 1) cout << ' ';
}
cout << endl;
}
return 0;
}
dfs做法
1 个赞
俞天行
(ytxqwq)
18
《根据真实事件改编》， @汪嘉乐 你真棒！不就我的改了点吗
不给
2 个赞