Scratch编程一级 题库
重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。
时间限制:1000
内存限制:65536
输入
输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入,用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG BCAD CBAD
样例输出
ACBFGED CDAB
#include <stdio.h>
#include <string.h>
void bulid(int n, char s1[],
char s2[]) // n是树的节点数,s1是记录先序遍历,s2中序遍历
{
if (n <= 0)
return; // 没有节点了,找到边界return
int p = strchr(s2, s1[0]) - s2;
// strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址
// 所以p是 s1[0]第一次出现在s2中的位置
bulid(p, s1 + 1, s2);
// 数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...
// 以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点
// s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)
bulid(n - p - 1, s1 + p + 1, s2 + p + 1);
// 数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)
// 以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点
// s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点
// )
printf("%c", s1[0]); // 输出
}
int main() {
char s1[10007], s2[10007]; // s1是树的前序遍历,s2是树的中序遍历
while (scanf("%s %s", s1, s2) != EOF) // 多组数据
{
bulid(strlen(s1), s1, s2);
printf("\n"); // 记得输出\n
}
return 0;
}
/*
先序遍历第一个节点一定是根节点。
中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。
后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。
*/逃离迷宫
你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。
时间限制:1000
内存限制:65536
输入
输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。
输出
每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。
样例输入
2 4 7 S... ###. .#E. ..#. 3 4 S.. ..# .#E
样例输出
YES NO
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
struct node {
int x, y;
int tcnt;
};
int m, t;
char mat[MAX_M][MAX_M];
int bfs(int x0, int y0, int x1, int y1) {
if (x0 == x1 && y0 == y1) {
return 0;
}
struct node nd = {x0, y0, 0};
int x, y;
struct node q[MAX_M * MAX_M];
int front = 0, rear = 0;
q[rear++] = nd;
while (front < rear) {
nd = q[front++];
x = nd.x;
y = nd.y;
if (x < m - 1) {
if (mat[x + 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x + 1][y] == '.') {
struct node newNode = {x + 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x + 1][y] = '*';
}
}
if (x > 0) {
if (mat[x - 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x - 1][y] == '.') {
struct node newNode = {x - 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x - 1][y] = '*';
}
}
if (y < m - 1) {
if (mat[x][y + 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y + 1] == '.') {
struct node newNode = {x, y + 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y + 1] = '*';
}
}
if (y > 0) {
if (mat[x][y - 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y - 1] == '.') {
struct node newNode = {x, y - 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y - 1] = '*';
}
}
}
return -1;
}
int main() {
int k, i, j, x0, y0, x1, y1, ans;
scanf("%d", &k);
while (k--) {
scanf("%d %d", &m, &t);
for (i = 0; i < m; i++) {
for (j = 0; j < m; j++) {
scanf(" %c", &mat[i][j]);
if (mat[i][j] == 'S') {
x0 = i;
y0 = j;
} else if (mat[i][j] == 'E') {
x1 = i;
y1 = j;
}
}
}
ans = bfs(x0, y0, x1, y1);
if (ans <= t && ans >= 0) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}电话号码
给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。
时间限制:1000
内存限制:65536
输入
第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。
样例输入
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
样例输出
NO YES
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int t;
int n;
int FLAG; // FLAG=1代表互不构成后缀,FLAG=0代表摸一个单词构成后缀
struct Node {
struct Node *next[10]; // 定义一个指针数组next,里面的元素都是Node类型的指针
int is_Cover; // 定义这个节点的访问次数
int is_End; // 定义这个节点是否是一个电话号的最后一个字符
};
void Init(Node *a) // 初始化节点i
{
memset(a->next, 0, sizeof(a->next)); // next[0]~next[9]都是指针NULL
a->is_Cover = 0;
a->is_End = 0;
}
// 内存友好型函数:释放内存
void DELETE(Node *root) {
for (int i = 0; i < 10; i++) {
if (root->next[i]) {
DELETE(root->next[i]);
} // 递归法释放内存
}
free(root); // 递归到底层,root->next[0~9]都是NULL,直接释放root即可
}
void insert(Node *root, char *temp) {
Node *p = root;
int id; // 0~9
while (*temp) // 字符串指针未到底
{
id = *temp - '0';
if (p->next[id] == NULL) {
p->next[id] = (Node *)malloc(sizeof(Node)); // 先申请内存空间
Init(p->next[id]); // 再对这个节点进行初始化
}
p = p->next[id]; // 指针往下移动
if (p->is_End) {
FLAG = 0;
} // 这个点是其他电话号的最后一个数字,包含着其他单词的前缀
p->is_Cover++;
temp++; // 字符指针向下移动
}
if (p->is_Cover > 1) {
FLAG = 0;
} // 执行到这里说明temp字符串是其他长字符串的前缀,temp字符串较短
p->is_End = 1; // 设置字符串末尾标志
}
int main() {
char ss[15];
cin >> t;
while (t--) {
Node *root = (Node *)malloc(sizeof(Node));
Init(root);
FLAG = 1; // 没有特殊情况不构成后缀
cin >> n;
while (n--) {
scanf("%s", ss);
if (FLAG) {
insert(root, ss);
} // 前面都没有前缀的发生,可以继续插入
}
if (FLAG == 0) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
DELETE(root); // 释放内存
}
return 0;
}移动路线
桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。
小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。
对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:
-------------------
|(2,1)|(2,2)|(2,3)|
-------------------
|(1,1)|(1,2)|(1,3)|
-------------------
蚂蚁共有3种移动路线:
路线1:(1,1) → (1,2) → (1,3) → (2,3)
路线2:(1,1) → (1,2) → (2,2) → (2,3)
路线3:(1,1) → (2,1) → (2,2) → (2,3)
时间限制:1000
内存限制:65536
输入
输入只有一行,包括两个整数m和n(0<m+n<=20),代表方格矩阵的行数和列数,m、n之间用空格隔开
输出
输出只有一行,为不同的移动路线的数目。
样例输入
2 3
样例输出
3
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 40;
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
int n, m, ans = 0;
bool flag = false;
struct node {
int x;
int y;
} st[N * N], tu[N * N][N * N];
int a[N * N];
bool ran_out(int x, int y) { return x < 1 || x > n || y < 1 || y > m; }
void fuzhi(int step) {
ans++;
a[ans] = step;
flag = true;
for (int i = 0; i <= step; i++) {
tu[ans][i].x = st[i].x;
tu[ans][i].y = st[i].y;
}
}
void dfs(int x, int y, int step) {
st[step].x = x;
st[step].y = y;
if (x == n && y == m) {
fuzhi(step);
return;
}
for (int i = 0; i < 2; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (!ran_out(xx, yy)) {
dfs(xx, yy, step + 1);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> m;
dfs(1, 1, 0);
printf("%d\n", ans);
for (int i = 1; i <= ans; i++)
return 0;
}移动办公
假设你经营着一家公司,公司在北京和南京各有一个办公地点。公司只有你一个人,所以你只能每月选择在一个城市办公。在第i个月,如果你在北京办公,你能获得Pi的营业额,如果你在南京办公,你能获得Ni的营业额。但是,如果你某个月在一个城市办公,下个月在另一个城市办公,你需要支付M的交通费。那么,该怎样规划你的行程(可在任何一个城市开始),才能使得总收入(总营业额减去总交通费)最大?
时间限制:1000
内存限制:65536
输入
输入的第一行有两个整数T(1 <= T <= 100)和M(1 <= M <= 100),T代表总共的月数,M代表交通费。接下来的T行每行包括两个在1到100之间(包括1和100)的的整数,分别表示某个月在北京和在南京办公获得的营业额。
输出
输出只包括一行,这一行只包含一个整数,表示可以获得的最大总收入。
样例输入
4 3 10 9 2 8 9 5 8 2
样例输出
31
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int main() {
int n; // ÔÂÊý
int m; // ½»Í¨·Ñ
int a, b;
cin >> n >> m;
int d[n][2];
for (int i = 0; i < n; i++) {
cin >> d[i][0] >> d[i][1];
}
for (int i = n - 2; i >= 0; i--) {
d[i][1] = d[i][1] + max(d[i + 1][0] - m, d[i + 1][1]);
d[i][0] = d[i][0] + max(d[i + 1][0], d[i + 1][1] - m);
}
cout << max(d[0][0], d[0][1]);
}青蛙的约会
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
时间限制:1000
内存限制:65536
输入
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
样例输入
1 2 3 4 5
样例输出
4
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return gcd;
}
ll inv(ll a, ll b, ll c) {
ll x, y;
ll gcd = exgcd(a, b, x, y);
if (c % gcd != 0)
return -1;
x *= c / gcd; // 得到当前情况下的一个x
b /= gcd; // 根据通解x = x0 + (b * t) / gcd 所以b = b / gcd
b = abs(
b); // 为了得到正数解,所以要abs,而且要在上一步/gcd之后,因为gcd可能是负的
ll ans = x % b;
if (ans < 0)
ans += b;
return ans;
}
int main() {
ll x, y, n, m, L;
cin >> x >> y >> m >> n >> L;
ll res = inv(m - n, L, y - x);
if (res == -1)
cout << "Impossible";
else
cout << res;
return 0;
}迷宫
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出
YES NO
#include <queue>
#include <stdio.h>
#include <string.h>
int m;
char c[100][100];
int xa, ya, xb, yb;
bool vis[100][100];
int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
int x;
int y;
int step;
} q[10000];
void bfs(int xa, int ya, int xb, int yb) {
int head = 1, tail = 1;
memset(vis, 0, sizeof(vis));
q[tail].x = xa;
q[tail].y = ya;
q[tail].step = 0;
tail++;
vis[xa][ya] = 1;
int flag = 1;
while (head < tail) {
int x = q[head].x;
int y = q[head].y;
int step = q[head].step;
if (x == xb && y == yb) {
flag = 0;
printf("YES\n");
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m && c[nx][ny] == '.' &&
vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q[tail].x = nx;
q[tail].y = ny;
q[tail].step = step + 1;
tail++;
}
}
head++;
}
if (flag == 1) {
printf("NO\n");
}
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", c[i]);
}
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
bfs(xa, ya, xb, yb);
}
return 0;
}玩具摆放
在一个4*4的方框内摆放了若干个相同的玩具。
某人想通过移动玩具,将这些玩具重新摆放成为他心中理想的状态。要求每次移动时,只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框,并且移动的目标位置不能已经放置有玩具。
请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。
时间限制:10000
内存限制:524288
输入
前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。
输出
一个整数,所需要的最少移动次数。保证初始状态可以达到目标状态。
样例输入
1111 0000 1110 0010 1010 0101 1010 0101
样例输出
4
提示
可以考虑将玩具局面表示为一个16 bit的整数,设置一个标志数组用来判重,用这个整数做下标找其对应标志位
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
// #include<cmath>
using namespace std;
const int INF = 9999999;
#define LL long long
inline int read() {
int x = 0, f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-')
f = -1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int N, E;
bool vis[65539];
char c;
int l = 1, r = 1;
struct data {
int st, k;
} Que[700001];
void BFS() {
Que[l].st = 0, Que[l].k = N;
int step, Now;
if (Que[l].k == E) {
printf("%d", Que[l].st);
return;
}
while (l <= r) {
Now = Que[l].k, step = Que[l].st;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (((Now >> ((4 - i) * 4 + 4 - j)) & 1)) {
for (int p = 0; p < 4; p++) {
if (p == 0 && i != 1 &&
!((Now >> ((4 - (i - 1)) * 4 + 4 - j)) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 8 - j))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 8 - j));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 1 && i != 4 &&
!((Now >> ((4 - (i + 1)) * 4 + 4 - j)) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 - j))]) {
Que[++r].k =
Now - (1 << ((4 - i) * 4 + 4 - j)) + (1 << ((4 - i) * 4 - j));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 2 && j != 1 &&
!((Now >> ((4 - i) * 4 + 4 - (j - 1))) & 1) &&
!vis[(1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j - 1)))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j - 1)));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 3 && j != 4 &&
!((Now >> ((4 - i) * 4 + 4 - (j + 1))) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j + 1)))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j + 1)));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
}
}
}
}
l++;
}
}
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int tmp = 16;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) {
cin >> c;
N = N + (1 << (tmp - 1)) * (c - '0');
tmp--;
}
vis[N] = true;
tmp = 16;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) {
cin >> c;
E = E + (1 << (tmp - 1)) * (c - '0');
tmp--;
}
BFS();
return 0;
}哥斯拉大战金刚
众所周知,哥斯拉和金刚是时代仇敌,大战一触即发。金刚为了打败哥斯拉,要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图,S表示金刚目前的位置,T表示地心空洞的入口,X表示障碍物,.表示平地。在前往地心空洞之前,金刚必须先获得一系列打开地心空洞的钥匙(在地图上通过数字1,2,…,k表示),并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙,金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外,同一种类的钥匙可能有多把,金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格,值得注意的是,哥斯拉为了阻挠金刚的计划,还在地图上设置了q个陷阱(在网格图中用G表示),金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱(这之后该陷阱即可被视为平地)。为了更好的掌握全局,请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。
时间限制:6000
内存限制:262144
输入
第一行输入两个整数n,m,表示网格图的大小。 接下来n行,每行输入m个字符,表示地图 1 ≤ n,m ≤ 100 1 ≤ k ≤ 9 1 ≤ q ≤ 7
输出
输出一行包含一个整数,表示金刚到达地心空洞入口所需要花费的最少步数。
样例输入
5 5 XX13X X.GXX S...T XXGXX ....2
样例输出
24
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct point {
int x, y;
short keys;
short fighted;
int steps;
short layout;
point(int inx, int iny, short k, short f, int s, short l)
: x(inx), y(iny), keys(k), fighted(f), steps(s), layout(l) {}
};
char flags[105][105][10][130];
int n, m;
int k, q;
char maze[105][105];
vector<pair<int, int>> traps;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int findTraps(int x, int y) {
for (int i = 0; i < q; i++) {
if (traps[i].first == x && traps[i].second == y)
return i;
}
}
int main() {
cin >> n >> m;
int startx, starty;
q = 0;
k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
if (maze[i][j] == 'G') {
q++;
traps.push_back(make_pair(i, j));
}
if (maze[i][j] > '0' && maze[i][j] <= '9')
k = max(k, maze[i][j] - '0');
}
}
queue<point> myqueues;
short oriLayout = (1 << q) - 1;
myqueues.push(point(startx, starty, 0, 0, 0, oriLayout));
memset(flags, 0, sizeof(flags));
flags[startx][starty][0][oriLayout] = 1;
while (!myqueues.empty()) {
point top = myqueues.front();
myqueues.pop();
if (maze[top.x][top.y] == 'T' && top.keys == k) {
cout << top.steps << endl;
break;
}
if (maze[top.x][top.y] == 'G' && top.fighted == 0) {
int index = findTraps(top.x, top.y);
short layout = top.layout & (~(1 << index));
myqueues.push(point(top.x, top.y, top.keys, 1, top.steps + 1, layout));
flags[top.x][top.y][top.keys][layout] = 1;
continue;
}
for (int i = 0; i < 4; i++) {
int tx = top.x + dx[i];
int ty = top.y + dy[i];
if (tx < 0 || tx >= n || ty < 0 || ty >= m)
continue;
if (maze[tx][ty] == 'X')
continue;
else if (maze[tx][ty] == 'G') {
if (flags[tx][ty][top.keys][top.layout])
continue;
int index = findTraps(tx, ty);
if ((top.layout >> index) & 1) // 还没打
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
else
myqueues.push(point(tx, ty, top.keys, 1, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
} else if (maze[tx][ty] == '.' || maze[tx][ty] == 'S' ||
maze[tx][ty] == 'T') {
if (flags[tx][ty][top.keys][top.layout])
continue;
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
} else {
int key = maze[tx][ty] - '0';
if (key == top.keys + 1) {
if (flags[tx][ty][key][top.layout])
continue;
myqueues.push(point(tx, ty, key, 0, top.steps + 1, top.layout));
flags[tx][ty][key][top.layout] = 1;
} else {
if (flags[tx][ty][top.keys][top.layout])
continue;
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
}
}
}
}
return 0;
}解题思路
思路:广搜题,属于较为复杂的一种,既要收集钥匙也要破坏陷阱。
状态包括:x,y坐标,keys表示现在收集的钥匙种数,fighted表示是否已经消灭陷阱,steps记录此时的步数,layout是陷阱的分布(用short变量表示)。
去重:xy坐标+钥匙+陷阱分布
地图上的标识有
‘.’:平地;‘X’:障碍,不能通过;‘T’:终点;‘S’:起点;‘G’:陷阱;1~9的数字:钥匙
起点和没有拿完钥匙的终点,不能拿的钥匙,破坏完的陷阱都当做平地处理
红与黑
有一间长方形的房子, 地上铺了红色、 黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上, 只能向相邻的黑色瓷砖移动。 请写一个程序, 计算你总共能够到达多少块黑色的瓷砖。
时间限制: 1000
内存限制: 65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
//解法1:深搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
char mp[N][N];//地图
int w, h, ct;//h:行数,w:ct:结果计数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
void dfs(int sx, int sy)
{
for(int i = 0; i < 4; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
ct++;
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
int stx, sty;//起始位置
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));//多组数据,注意状态还原
ct = 1;
vis[stx][sty] = true;
dfs(stx, sty);
cout << ct << endl;
}
return 0;
}//解法2:广搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
char mp[N][N];//地图
int w, h;//w:列数 h:行数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
int bfs(int sx, int sy)//传入起始位置
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy));
int ct = 1;//计数,看可以到达几个黑色格子
while(que.empty() == false)
{
Node u = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
int x = u.x + dir[i][0], y = u.y + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
que.push(Node(x, y));
ct++;
}
}
}
return ct;
}
int main()
{
int stx, sty;
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));
cout << bfs(stx, sty) << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1001
using namespace std;
int m,n;
char ch;
int maps[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0&&maps[nx][ny]==1)
{
vis[nx][ny]=1;
cnt++;
dfs(nx,ny);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
{
int x,y;
cnt=1;
memset(vis,0,sizeof(vis));
memset(maps,0,sizeof(maps));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
if(ch=='@')
{
x=i;
y=j;
maps[i][j]=1;
}
if(ch=='.')
maps[i][j]=1;
if(ch=='#')
maps[i][j]=0;
}
vis[x][y]=1;
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}Project Summer 游戏
小 I 和小 B 最近沉迷一款叫做《Project Summer》 的游戏, 小 I 扮演这个游戏中需要逃生的无辜者(Innocent), 小 B 扮演这个游戏中抓住无辜者, 阻止其逃生的背叛者(Betrayer)。
这个游戏的地图是一个 N 行 M 列 的矩形, 每个格点表示一个位置。
'#' 表示地图中的障碍物, '.' 表示地图中的空地, 此外, 地图中还有只有背叛者才能使用的传送门, 用小写字母 'a' - 'z' 标记, 它们在地图上成对出现。
角色可以花费 1 单位的时间从一个格子走到上下左右相邻的 4个空地中的另一个格子(不可以走出地图边界或者走到障碍物上)。此外, 当小 B 扮演的背叛者走到一个传送门上时, 他可以花费 1 单位的时间从当前格子传送到与当前格子相同字母的另一个传送门处(他也可以选择不传送, 此时没有花费任何时间, 待在原地不动)。
传送是双向的。 比如, 现在小 B 走到了标记为 'a' 的格子上, 那么他可以选择花费一单位的时间传送到另一个标记为 'a' 的格子上, 也可以选择不传送, 那么他就待在原地不动。
现在, 小 I 被小 B 的陷阱困住了, 无法移动。 给出地图上小 B 和小 I 所在的格子(他们都站在空地上), 求小 B 最少需要花费多少时间才能走到小 I 所在的格子抓住他。 如果小 I 无法抓住小 B, 输出 -1
时间限制: 1000
内存限制: 65536
输入
第一行一个数字 T, 表示数据组数。 接下来描述 T 组数据, 每组数据最开始是两个正整数 N, M 表示地图是 N 行 M 列的矩形。 接下来 N 行, 每行 M 个字符, 表示地图。 在地图上, 用 '.' 表示空地,'#' 表示障碍物, 'a'-'z' 表示传送门, 'B' 表示小 B 的初始位置, 'I' 表示小 I 的初始位置。 对于每组数据, 保证在地图上标记相同的传送
门恰好出现两次。 T,N,M <= 100
输出
T 行, 第 i 行输出 'Case #i: t', 表示第 i 组数据的答案是 t. 小 B 最少需要 t 单位时间才能走到小 I 所在的格子。 如果小 I 无法抓住小B, 输出 -1
样例输入
3 5 5 Bx#.. #a.#. ..... ##..# .x.aI 5 5 BIa.a x#.x. .#.## ..... ##### 2 2 B# #I
样例输出
Case #1: 4 Case #2: 1 Case #3: -1
提示
对于第一组数据, 假设行从上到下标号 1 到 5, 列从左到右标号 1到 5, 小 B 初始在 (1, 1)。 小 B 的最优路线是: (1, 1) -> (1, 2) -> (2,2) -> (5, 4) -> (5, 5)。 也就是走到标记为 x 的传送门时忽略传送门, 走到标记为 a 的传送门时使用传送门。 对于第二组数据, 小 B 直接花费 1 单位时间向右走一格就可以抓住小 I, 故输出 1。 对于第三组数据, 小 B 无法走到小 I 所在的位置上, 故输出 -1。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int T, N, M;
int ii, jj;
int directs[4][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[100][100];
int visited[100][100];
struct Data {
int i, j, t;
Data(int _i, int _j, int _t) : i(_i), j(_j), t(_t) {}
};
Data gogogo(const Data &d) {
char c = a[d.i][d.j];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (a[i][j] == c && !(d.i == i && d.j == j)) {
return Data(i, j, d.t + 1);
}
}
}
return d;
}
int main() {
cin >> T;
for (int t = 1; t <= T; ++t) {
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> a[i][j];
if (a[i][j] == 'B') {
ii = i;
jj = j;
}
}
}
queue<Data> q;
memset(visited, -1, sizeof(visited));
q.push(Data(ii, jj, 0));
visited[ii][jj] = 0;
bool flag = 0;
while (!q.empty()) {
Data cur = q.front();
if (a[cur.i][cur.j] == 'I') {
flag = 1;
break;
}
q.pop();
int ni, nj, nt;
for (int d = 0; d < 4; ++d) {
ni = cur.i + directs[d][0];
nj = cur.j + directs[d][1];
nt = cur.t + 1;
if (ni >= 0 && ni < N && nj < M && nj >= 0 && a[ni][nj] != '#' &&
(visited[ni][nj] == -1 || nt < visited[ni][nj])) {
visited[ni][nj] = nt;
q.push(Data(ni, nj, nt));
}
}
// 气!isalpha函数在OJ上会被判错
if (a[cur.i][cur.j] <= 'z' && a[cur.i][cur.j] >= 'a') {
Data nd = gogogo(cur);
if (visited[nd.i][nd.j] == -1 || nd.t < visited[nd.i][nd.j]) {
visited[nd.i][nd.j] = nd.t;
q.push(nd);
}
}
}
cout << "Case #" << t << ": " << ((flag) ? q.front().t : -1) << endl;
}
}矩形数量
给出平面上一些点(少于50个),坐标都是整数(|xi|,|yi| <= 109),有可能重复。问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同,就算相同的矩形)
时间限制:1000
内存限制:65536
输入
第一行一个整数T(T <= 100)表示测试数据的组数 对于每组数据 第一行一个整数n,表示点的数量 下面n行每行两个整数xi,yi表示点的坐标
输出
T行,每行一个整数表示以这些点为顶点的平行于坐标轴的矩形个数
样例输入
1 7 0 0 0 1 0 2 1 0 1 1 1 2 0 0
样例输出
3
提示
直接穷举即可。
#include <bits/stdc++.h>
using namespace std;
int t, n, ans;
struct node
{
int x, y;
} a[55];
vector<node> v;
bool cmp(node x, node y)
{
if (x.x != y.x)
return x.x < y.x;
return x.y < y.y;
}
long long dist(node x, node y)
{
return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--)
{
cin >> n;
ans = 0;
v.clear();
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1, cmp);
v.push_back(a[1]);
for (int i = 2; i <= n; i++)
{
if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)
v.push_back(a[i]);
}
for (int i = 0; i < v.size() - 3; i++)
{
for (int j = i + 1; j < v.size() - 2; j++)
{
for (int k = j + 1; k < v.size() - 1; k++)
{
for (int w = k + 1; w < v.size(); w++)
{
if (dist(v[i], v[w]) == dist(v[j], v[k]) && (v[i].y == v[k].y) && (v[i].x == v[j].x) && (v[k].x == v[w].x))
{
ans++;
}
}
}
}
}
cout << ans << "\n";
}
return 0;
}我变成一只喷火龙啦
一、准备工作
(1)删除默认小猫角色,添加角色:Dragon,Wizard;
(2)删除默认空白背景,添加背景:Forest。
二、功能实现
(1)点击绿旗,设置恐龙大小为50,初始造型为dragon-b,初始位置在舞台左侧;设置巫师旋转方式为左右翻转,初始位置在舞台右侧,面向-90°方向;

(2)1秒后,恐龙移动到巫师面前,并切换造型为dragon-c变成喷火龙,同时巫师说“你好!”2秒。



小猫过生日
1.准备工作
(1)保留小猫角色,添加角色:Cake;
(2)添加背景:Party。
2.功能实现
(1)小猫和蛋糕的初始位置如下图所示,小猫初始造型为cat-a,蛋糕初始造型为cake-a;

(2)点击绿旗,等待1秒后,小猫从左到右切换着造型走到蛋糕旁边;

(3)鼠标点击蛋糕,播放完整的生日快乐歌“Birthday”后,换成造型cake-b。

小猫程序

小猫程序

评分标准:
(1)能够正确导入背景和角色;(3分)
(2)小猫和蛋糕的初始造型、初始位置正确;(3分)
(3)小猫能切换造型走到蛋糕旁边;(3分)
(4)点击蛋糕,蛋糕能播放生日快乐歌,能切换造型;(5分)
(5)能完整播完生日歌后才切换造型。(1分)
火箭升空
1.准备工作
(1)删除默认小猫角色,添加角色:Rocketship;
(2)添加背景:Stars、Galaxy。
2.功能实现
(1)火箭初始位置在舞台的下端,初始造型为rocketship-a, 初始背景为Stars;

(2)点击绿旗,火箭切换着造型向上移动;

(3)当火箭到达大约中间的位置,背景切换成Galaxy;

(4)接着继续向上移动到顶部,过程中会继续切换造型。


评分标准:
(1)删除默认小猫角色,添加Rocketship角色,添加背景Stars、Galaxy;(3分)
(2)火箭初始位置为舞台下端,初始造型为rocketship-a,初始背景为Stars;(3分)
(3)点击绿旗,移动垂直向上移动,移动过程中会切换造型;(3分)
(4)当火箭到达大约中间的位置,背景切换成Galaxy;(3分)
(5)接着继续向上移动到顶部,过程中会切换造型。(3分)
足球射门训练
1.准备工作
(1)保留默认小猫角色,添加足球角色:Soccer Ball;
(2)给足球角色,添加声音:Cheer;
(3)添加背景:Soccer 2。
2.功能实现
(1)小猫的初始位置为(-14,-50),小猫初始造型为造型1,足球的初始位置为(138,-71);

(2)等待1秒后,小猫每隔0.5秒,水平向右,移动30,切换一次造型,这样移动四次后,到达足球边上;

(3)足球等待3秒后,水平向右移动到舞台最右端的球网处,播放Cheer声音。

标准答案:
参考程序:
小猫程序

足球程序

试题解析:
评分标准:
(1)添加角色Soccer Ball;(1分)
(2)添加背景Soccer 2;(1分)
(3)小猫的初始位置和初始造型设置正确;(2分)
(4)足球的初始位置设置正确;(1分)
(5)小猫能一面切换造型,一面移动,能水平移动到足球边上;(4分)
(6)当小猫移动到足球边上后,足球能水平向右移动,一直移动到舞台最右边;(4分)
(7)足球能播放Cheer声音。(2分)