蓝桥杯模拟赛 3
A题 特殊年份
签到题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 10010, M = 1e9 + 7;
int ans;
void solve() {
for (int i = 0; i < 5; i++) {
int n;
cin >> n;
if ((n / 1000 == n % 100 / 10) && (n / 100 % 10 + 1 == n % 10))
ans++;
}
cout << ans;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
B题 小平方
按照题目意思模拟一遍就可以了，但要小心除而会向零取整，强制转化成浮点数double
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 10010, M = 1e9 + 7;
int ans;
void solve() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int res = (i * i) % n;
if (res < (D) n / 2 )ans++;
}
cout << ans;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
C题 砝码称重
dp问题，使用集合的思想来做，f[i,j]的含义为前i个物品总重量不超过j的选的方法!，以最后一次状态来分析，分为不拿砝码f[i-1,j]，加到左边f[i-1,j-w]，加到右边f[i-1,j+w]，这三种状态只要一个非空，就非空，但是出现了j-w有可能是负数，所以可以给所有的j加一个偏移量，或者使用镜像解题f[i-1,abs(j-w)]，初始状态f[0][0]=1。
偏移量，防止数组下标越界。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int w[110];
bool f[110][2*N];
int n, sum;
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> w[i], sum += w[i];
f[0][N] = true;
for (int i = 1; i <= n; i++) {
for (int j = -sum; j <= sum; j++) {
f[i][j + N] = f[i - 1][j + N];
if (j - w[i] >= -sum)f[i][j + N] |= f[i - 1][j - w[i] + N];
if (j + w[i] <= sum)f[i][j + N] |= f[i - 1][j + w[i] + N];
}
}
int res = 0;
for (int i = 1; i < N * 2; i++)
if (f[n][i + N] == 1)res++;
cout << res << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
镜像运用绝对值
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int w[110];
bool f[110][2*N];
int n, sum;
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> w[i], sum += w[i];
f[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
f[i][j] = f[i - 1][j] || f[i - 1][j + w[i]] || f[i - 1][abs(j - w[i])];
}
}
int res = 0;
for (int i = 1; i < N * 2; i++)
if (f[n][i])res++;
cout << res << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
如果暴力来做会超时，dfs，只有一半的分数
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 110, M = 1e5 + 10;
int a[N], st[M];
int n, sum;
void dfs(int s,int u) {
if (u > n) {
if(s>0)st[s]=1;
return ;
}
dfs(s + a[u], u + 1);
dfs(s, u + 1);
dfs(abs(s - a[u]), u + 1);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i],sum+=a[i];
dfs(0, 1);
int ans = 0;
for (int i = 1; i < M; i++) {
if (st[i])ans++;
}
cout << ans << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
D题 完全平方数
不能暴力做，会超时，使用分解质因的方式求答案，一个完全平方数的质因子的次数一定是偶数，求一个数最小乘以多少是完全平方数，就求这个数的质因子的次数，如果是偶数就不成，如果是奇数就乘以质因子，次数就变成偶数了，最后在判断剩余的n是不是大于一，如果是还有一个质因子的次数是奇数，再乘以它就是答案。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
ll n;
void solve() {
cin >> n;
ll res = 1;
for (ll i = 2; i * i <= n; i++) {
int cnt = 0;
if (n % i == 0) {
while (n % i == 0)cnt++, n /= i;
if (cnt & 1)res *= i;
}
}
if (n > 1)res *= n;
cout << res << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
E题 时间显示
注意单位是毫秒，先转化成秒，将一整天所需要的秒去掉，再一个一个求小时，分钟，秒。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef double D;
const int N = 10010, M = 1e9 + 7;
int ans;
void solve() {
ll n;
cin>>n;
n/=1000;
ll day=24*60*60;
int k=n%day;
ll s=k%60;
ll h=k/3600;
ll m=(k-h*3600)/60;
printf("%02lld:%02lld:%02lld",h,m,s);
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
H题 负载均衡
对每个电脑工作结束的时间，用一个对来进行维护，把每次结束时间再开始时间之前的电脑都删掉计算算力。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 2e5 + 10, M = 1e5 + 10;
priority_queue<PII,vector<PII>,greater<PII>> q[N];
int n,m;
int aa[N];
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> aa[i];
while (m--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
while (q[b].size() && q[b].top().first <= a) {
aa[b] += q[b].top().second;
q[b].pop();
}
if (aa[b] < d)cout << "-1" << endl;
else {
q[b].push({a + c, d});
aa[b] -= d;
cout << aa[b] << endl;
}
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
单链表
单链表的复习，建图的基础。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int h=-1,e[N],ne[N],idx=0;
void add_head(int x) {
e[idx] = x;
ne[idx] = h;
h = idx++;
}
void add(int k,int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
void remove(int k) {
ne[k] = ne[ne[k]];
}
void solve() {
int m;
cin >> m;
while (m--) {
char ch;
cin >> ch;
if (ch == 'H') {
int x;
cin >> x;
add_head(x);
} else if (ch == 'D') {
int k;
cin >> k;
if (!k)h = ne[h];
remove(k - 1);
} else {
int k, x;
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = h; i != -1; i = ne[i])cout << e[i] << ' ';
cout << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
模拟栈
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int m, tt;
int stk[N];
void solve() {
cin >> m;
while (m--) {
string s;
int n;
cin >> s ;
if (s == "push") {
cin >> n;
stk[++tt] = n;
}
else if (s == "pop") tt--;
else if (s == "empty") {
if (tt == 0)cout << "YES" << endl;
else cout << "NO" << endl;
} else cout << stk[tt] << endl;
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
模拟队列
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int m, tt, hh;
int q[N];
void solve() {
cin >> m;
while (m--) {
string s;
int n;
cin >> s;
if (s == "push") {
cin >> n;
q[tt++] = n;
} else if (s == "pop") hh++;
else if (s == "empty") {
if (hh >= tt)cout << "YES" << endl;
else cout << "NO" << endl;
} else cout << q[hh] << endl;
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
双链表
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int idx,e[N],l[N],r[N];
void init(){
l[1]=0,r[0]=1,idx=2;
}
void add(int k,int x) {
e[idx] = x;
l[idx] = k, r[idx] = r[k];
l[r[k]] = idx, r[k] = idx++;
}
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
void solve() {
init();
int m;
cin >> m;
while (m--) {
string op;
int k, x;
cin >> op;
if (op == "L") {
cin >> x;
add(0, x);
} else if (op == "R") {
cin >> x;
add(l[1], x);
} else if (op == "D") {
cin >> k;
remove(k + 1);
} else if (op == "IR") {
cin >> k >> x;
add(k + 1, x);
} else {
cin >> k >> x;
add(l[k + 1], x);
}
}
for (int i = r[0]; i != 1; i = r[i])cout << e[i] << ' ';
cout << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
SMU Winter 2023 Round #12 (Div.2)
A题 kk画猪
签到题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
void solve() {
string s;
cin >> s;
printf(R"( (\____/)
/ @__@ \
( (oo) )
`-.~~.-'
/ \
@/ \_
(/ / \ \)
WW`----'WW
)");
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
B题 kk学几何
签到题
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int fa[N],a[N];
void solve() {
int T;
cin >> T;
double ans = 0;
while (T--) {
int n;
cin >> n;
if (n == 1) {
int r;
cin >> r;
ans += 3 * r * r;
} else if (n == 2) {
int l, h;
cin >> l >> h;
ans += (D) (l * h) / 2;
} else if (n == 3) {
int l, w;
cin >> l >> w;
ans += l * w;
}
}
printf("%.1f\n", ans);
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
C题 kk算日期
本题要注意题目，公元0年不存在，看是看见了，没转过弯来，公元0年不存在，那么1后面就是-1，所以当所求公元年数小于等于0时，要再减1，再求绝对值计算即可。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int fa[N],a[N];
void solve() {
int n, m;
cin >> n >> m;
n += m;
if (n <= 0)n--;
n = abs(n);
if (n % 4 == 0 && n % 100 != 0 || n % 400 == 0)
cout << 29 << endl;
else cout << 28 << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
cin >> h_h;
while (h_h--) solve();
return 0;
}
G题 kk看跳舞
问给出的数字首尾连接在一起能不能构成一个依次增加1或减少1的全排列。我们可以先找起始位置1位置然后再从两边判断，哪边是二就往哪边走，遍历到头或尾的时候更新成尾或头，直到遍历到全排列的最后一个数字，并计数cnt，看看cnt是不是和全排列最后一个数字相等，是就可以，不是就不可以。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 10010, M = 1e5 + 10;
int fa[N],a[N];
void solve() {
int n;
cin >> n;
int start;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 1)start = i;
}
int cnt = 1;
if ((a[start - 1] == 2 && start - 1 >= 1) || (start - 1 < 1 && a[n] == 2)) {
while (1) {
cnt++;
if (start - 1 < 1)start = n + 1;
if (a[--start] == n)break;
}
} else if ((a[start + 1] == 2 && start + 1 <= n) || (start + 1 > n && a[1] == 2)) {
while (1) {
cnt++;
if (start + 1 == n + 1)start = 0;
if (a[++start] == n)break;
}
}
if (cnt == n)cout << "YES" << endl;
else cout << "NO" << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
cin >> h_h;
while (h_h--) solve();
return 0;
}
H题 kk与十佳
要考虑所以的情况，所有是正数，所有是负数，负数和正数都有，有负数情况下还要考虑负数的奇偶。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 30010, M = 1e5 + 10;
vector<int>a,b;
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0)a.push_back(x);
else b.push_back(x);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a.size() == 0) {
if (b.size() % 2 == 0)cout << b[0];
else cout << b[b.size() - 1];
} else if (b.size() == 0)cout << a[0];
else {
if (b.size() % 2 != 0)cout << b[b.size() - 1];
else cout << a[0];
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
I题 kk买股票
本题数据范围是1e5，用两重循环显然会超时，所以可以使用双指针来维护区间，我们保证区间的头是最小的，区间的尾是最大的，所以没个数都判断一下更新左右两端，并且左端点不能大于等于右端点，当大于时，要更新右端点。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int n;
int a[N];
void solve() {
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
int mn = 1000000, mx = 0;
int x, y;
for (int i = 1, j = 0; j < n;) {
if (a[i] > mx && i < n)mx = a[i], i++, x = i;
else i++;
if (a[j] < mn)mn = a[j], j++, y = j;
else j++;
if (j >= i)mx = a[j + 1], i = j + 1;
}
if (x - y <= 0)cout << 0 << endl;
else cout << mx - mn << endl;
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
J题 kk与英语
就是简单的字符串模拟,注意读入有空格的字符串用scanf或getline。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e5 + 10;
int n;
int a[N];
void solve() {
string s;
getline(cin, s);
cout << s[0];
for (int i = 1; i < s.size(); i++) {
if (s[i] == 'i' && s[i + 1] == 's' && s[i - 1] == ' ' && s[i + 2] == ' ') {
cout << "was";
i++;
continue;
}
cout << s[i];
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
KMP字符串
讲述怎么使用时间复杂度更低的方法寻找子串，感觉使用了双指针的算法。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 100010, M = 1e6 + 10;
int n, m;
char s[M], p[N];
int ne[N];
map<string,int> mp;
set<string>st;
void solve() {
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == n) {
printf("%d ", i - n);
j = ne[j];
}
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
献给()阿尔吉侬的花束
最简单的bfs的题目，好像dfs也可以。，不可以求最短距离，权值为1。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 210, M = 1e5 + 10;
int n,m;
char g[N][N];
int dist[N][N];
bool vis[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
int bfs(PII Start,PII End) {
queue<PII> q;
//memset(dist, -1, sizeof dist);
q.push(Start);
dist[Start.f][Start.s] = 0;
vis[Start.f][Start.s] = true;
while (!q.empty()) {
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int xx = dx[i] + t.f, yy = dy[i] + t.s;
if (xx < 0 || xx >= n || yy < 0 || yy >= m)continue;
if (vis[xx][yy])continue;
if (g[xx][yy] == '#')continue;
dist[xx][yy] = dist[t.f][t.s] + 1;
if (End == make_pair(xx, yy))return dist[xx][yy];
q.push({xx, yy});
vis[xx][yy] = true;
}
}
return -1;
}
void solve() {
int T;
cin >> T;
while (T--) {
memset(dist, 0, sizeof dist);
memset(vis, false, sizeof vis);
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
PII start, end;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 'S')start = (make_pair(i, j));
else if (g[i][j] == 'E')end = (make_pair(i, j));
}
}
int dis = bfs(start, end);
if (dis == -1)cout << "oop!" << endl;
else cout << dis << endl;
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
红与黑
Flood fill模型
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#define IOS ios::sync_with_stdio(false)
#define CC cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int ,int> PII;
typedef double D;
const int N = 210, M = 1e5 + 10;
int n,m;
char g[N][N];
int dist[N][N];
bool vis[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
int dfs(int x,int y) {
int cnt = 1;
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && g[xx][yy] == '.')
cnt += dfs(xx, yy);
}
return cnt;
}
void solve() {
while (cin >> m >> n) {
if (n == 0 && m == 0)break;
memset(vis, false, sizeof vis);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
int x,y;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '@')
x=i,y=j;
cout << dfs(x,y) << endl;
}
}
int main() {
IOS;
CC;
int h_h = 1;
//cin >> h_h;
while (h_h--) solve();
return 0;
}
京公网安备 11010502036488号