首页 › 题库 › Scratch编程考级 › 4.1 移动

Scratch编程一级 题库

共 85 道题 ,第 5 / 5 页 · 按题型筛选,点「查看答案」核对解析
81 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

玩具摆放

在一个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;
}
题目详情
82 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

哥斯拉大战金刚

众所周知,哥斯拉和金刚是时代仇敌,大战一触即发。金刚为了打败哥斯拉,要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个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的数字:钥匙

起点和没有拿完钥匙的终点,不能拿的钥匙,破坏完的陷阱都当做平地处理

题目详情
83 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

红与黑

有一间长方形的房子, 地上铺了红色、 黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上, 只能向相邻的黑色瓷砖移动。 请写一个程序, 计算你总共能够到达多少块黑色的瓷砖。

时间限制: 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;
}
题目详情
84 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

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;
  }
}
题目详情
85 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

矩形数量

给出平面上一些点(少于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;
}
题目详情