U5-7-图的概念与存储
原题链接：67324.4.0U5笔记合集
2025-09-27 15:50:56
发布于：江苏
3阅读
0回复
0点赞
一、上节课作业部分
1. 细胞数量
#include <bits/stdc++.h>
using namespace std;
struct node {
int x, y;
};
bool mp[205][205];
int n, m, ans;
char ch;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
void bfs(int x, int y)
{
mp[x][y] = 0;
ans++;
queue<node> q;
q.push({x, y});
while (q.size()) {
node t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int a = t.x + dx[i];
int b = t.y + dy[i];
if (mp[a][b] == 0) continue; //如果不是细胞直接跳过
q.push({a, b});
mp[a][b] = 0;
}
}
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> ch;
if (ch != '0') mp[i][j] = true; //细胞
else mp[i][j] = false; //不是细胞
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 如果当前位置没被搜索过且是数字则带入搜索
if (mp[i][j]) bfs(i, j);
}
}
cout << ans << endl;
return 0;
}
/*
样例组
输入#1
输出#1
4 10
0234500067
1034560500
2045600671
0000000089
4
*/
2. 打开转盘锁
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, ans;
cin >> n >>m;
cout << ans;
return 0;
}
/*
打开转盘锁
题目描述
有一个密码锁，密码是4位数字，每次你可以选择下列两种操作之一
1、将某一位数字增加1，如果对9操作将会变为1
2、将某一位数字减少1，如果对1操作将会变为9
给出锁现在的数字和能开锁的数字，问最少进行几次操作可以开锁
提示
数据范围：
两个四位数字
输入格式
给出两个四位数字，表示锁现在的数字和开锁的数字
输出格式
对于每组测试，输出最少操作次数
样例组
输入#1
1234
5678
输出#1
16
1 2 3 4 5 6 7 8 9
1
9
样例说明：
第一位(1->5),拨动了4次.
第二位(2->6),拨动了4次.
第三位(3->7),拨动了4次.
第四位(4->8),拨动了4次.
一共拨动16次。
*/
二、课堂案例部分
#include <bits/stdc++.h>
using namespace std;
int mp[105][105];
int n, m, q;
int main(){
memset(mp, 0x3f, sizeof mp);
cin >> n >> m >> q;
int a, b, w;
//输入m条遍
for (int i=1; i<=m; i++){
cin >> a >> b >> w;
mp[a][b] = mp[b][a] = min(w, mp[a][b]); //存图
}
//输入q个建议， 判断是否新建
while (q--){
cin >> a >> b >> w;
if (mp[a][b] > w) cout<<"Accepted"<<endl;
else cout << "Cancel" << endl;
}
return 0;
}
/*
输出格式
对于每个 x,y 如果通过输出 Accepted，否则输出 Cancel
样例组
输入#1
5 5 2
1 2 3
2 3 4
3 4 5
4 5 6
5 1 7
1 2 2
5 1 8
输出#1
Accepted
Cancel
*/
这里空空如也
有帮助，赞一个