首页 › 题库 › C/C++编程考级 › 4 图论基础

C/C++编程七级 题库

共 10 道题 · 按题型筛选,点「查看答案」核对解析
章节 4 图论基础 清除
1 判断题 偏易 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

Floyd算法可以求解有负权边的图的最短路径,但不能处理负权环。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
2 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

走出迷宫

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。

时间限制:1000

内存限制:65536

输入

第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

3 3
S#T
.#.
...

样例输出

6
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, m, p[10008], q[10008], ans[108][108], qx, qy, zx, zy;
char a[108][108];
int xx[5] = {0, 1, -1, 0, 0};
int yy[5] = {0, 0, 0, 1, -1};
void bfs() {
  a[qx][qy] = '#';
  ans[qx][qy] = 0;
  int head = 1;
  int tail = 1;
  p[1] = qx;
  q[1] = qy;
  while (head <= tail) {
    for (int i = 1; i <= 4; i++) {
      int h = p[head] + xx[i];
      int l = q[head] + yy[i];
      if (a[h][l] != '#' && h >= 1 && l >= 1 && h <= n && l <= m) {
        a[h][l] = '#';
        tail++;
        p[tail] = h;
        q[tail] = l;
        ans[h][l] = ans[p[head]][q[head]] + 1;
        if (h == zx && l == zy) {
          cout << ans[h][l] << endl;
          return;
        }
      }
    }
    head++;
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      if (a[i][j] == 'S') {
        qx = i;
        qy = j;
      }
      if (a[i][j] == 'T') {
        zx = i;
        zy = j;
      }
    }
  }
  bfs();

  return 0;
}
题目详情
3 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

拯救公主

多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。

    身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。

    你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。

    地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。

时间限制:1000

内存限制:65536

输入

第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。

输出

对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。

样例输入

1
7 8 2
........
..S..#0.
.##..1..
.0#.....
...1#...
...##E..
...1....

样例输出

11
答案与解析
参考答案
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
struct POINT {
  int x, y, tot;
  bool get_jewel[7], enchantment;
} point, door;
int main() {
  int k, F[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
  scanf("%d", &k);
  for (int kk = 1; kk <= k; kk++) {

    queue<POINT> que;
    int r, c, needkind, door_coord[15][2] = {}, sdoor_coord = 0;
    char maze[205][205] = {};
    bool walked[205][205][35] = {}, finish = false;
    scanf("%d%d%d", &r, &c, &needkind);
    for (int i = 0; i < r; i++) {
      scanf("%s", maze[i]);
      for (int j = 0; j < c; j++) {
        if (maze[i][j] == 'S') {
          memset(point.get_jewel, false, sizeof(point.get_jewel));
          point.x = i;
          point.y = j;
          point.tot = 0;
          point.enchantment = true;
        }
        if (maze[i][j] == '$') {
          door_coord[sdoor_coord][0] = i;
          door_coord[sdoor_coord++][1] = j;
        }
      }
    }
    que.push(point);
    while (!que.empty()) {
      for (int i = 0; i < 4; i++) {
        point = que.front();
        point.tot++;
        point.x += F[i][0];
        point.y += F[i][1];
        if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
            maze[point.x][point.y] == '#')
          continue;
        if ('0' <= maze[point.x][point.y] && maze[point.x][point.y] <= '4')
          point.get_jewel[maze[point.x][point.y] - '0'] = true;
        int sget_jewel = 0, ss = 0;
        for (int i = 0; i < 5; i++)
          if (point.get_jewel[i])
            sget_jewel += pow(2, i), ss++;
        if (walked[point.x][point.y][sget_jewel])
          continue;
        walked[point.x][point.y][sget_jewel] = true;
        if (ss >= needkind)
          point.enchantment = false;
        if (maze[point.x][point.y] == '$') {
          door = point;
          for (int i = 0; i < sdoor_coord; i++)
            if (door_coord[i][0] != point.x || door_coord[i][1] != point.y) {
              door.x = door_coord[i][0];
              door.y = door_coord[i][1];
              que.push(door);
            }
        }
        if (maze[point.x][point.y] == 'E' && !point.enchantment) {
          printf("%d\n", point.tot);
          finish = true;
        }
        if (finish)
          break;
        que.push(point);
      }
      if (finish)
        break;
      que.pop();
    }
    if (!finish)
      printf("oop!\n");
  }
  return 0;
}
// 参考答案2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define N 210
using namespace std;
int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}};
int dp[N][N][1 << 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans;
char map[N][N];
struct node {
  int x, y, step, key;
  node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){};
};
bool check(int key) {
  int cnt = 0;
  for (int i = 0; i <= 5; i++)
    if ((key >> i) & 1)
      cnt++; // 位运算 统计这条路上可获不同种类的宝石数量
  if (cnt >= k)
    return 1;
  return 0;
}
int bfs(int x, int y) {
  queue<node> que; // 根据结构体 定义队列que
  dp[x][y][0] = 1;
  node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量
  que.push(now);        // 进队
  while (!que.empty()) // 当队列不为空时  .empty()-->若队列为空返回1;
  {
    now = que.front();          // 把队头的值赋给now这个结构体上
    que.pop();                  // 弹出队首
    for (int i = 0; i < 4; i++) // 上下左右四个执行方案
    {
      int xx = now.x + dir[0][i]; // 具体变动
      int yy = now.y + dir[1][i];
      int step = now.step; // 步数
      int key = now.key;   //
      if (xx < 0 || xx >= n || yy < 0 || yy >= m)
        continue; // 判断边界
      if (dp[xx][yy][key])
        continue; // 若在队中 不走
      if (map[xx][yy] == '#')
        continue;                           // 禁区 不走
      if (map[xx][yy] == 'E' && check(key)) // 既到达营救点 且 宝石够数
      {
        return step + 1; // 返回步数 //结束遍历
      }
      if (isdigit(map[xx][yy])) //
      {
        dp[xx][yy][key] = 1;                    // 标记 相当于vis
        key = key | (1 << (map[xx][yy] - '0')); // 记录宝石
        que.push(node(xx, yy, step + 1, key));  // 进队
      }
      if (map[xx][yy] == '.') // 普通地带
      {
        dp[xx][yy][key] = 1; // 标记
        que.push(node(xx, yy, step + 1, key));
      }
      if (map[xx][yy] == '$') // 传送门
      {
        dp[xx][yy][key] = 1;                   // 标记
        que.push(node(xx, yy, step + 1, key)); // 进队
        for (int j = 1; j <= tot; j++)         // 遍历 方案
        {
          xx = trans[j][0], yy = trans[j][1];
          if (!dp[xx][yy][key]) {
            dp[xx][yy][key] = 1;                   // 标记
            que.push(node(xx, yy, step + 1, key)); // 进队
          }
        }
      }
    }
  }
  return -1; // 若遍历完还没返回 就说明没有可行方案
}
main() {
  cin >> T; // 组数
  while (T--) {
    memset(dp, 0, sizeof(dp));
    tot = 0;
    num = 0; // 初始化
    scanf("%d%d%d", &n, &m, &k);
    // cin>>n>>m>>k;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) {
        cin >> map[i][j];
        // scanf("%c",&map[i][j]);还是没搞明白为什么不能用scanf和getchar
        // map[i][j]=getchar();
        if (map[i][j] == 'S')
          x = i, y = j, map[i][j] = '.'; // 标记起点
        if (map[i][j] == '$')
          trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门
        if (isdigit(map[i][j]))
          num++; // 判断是否是宝石(数字)
      }
    if (k > num) {
      printf("oop!\n");
      continue;
    } // 没有足够的宝石
    ans = bfs(x, y);
    if (ans == -1)
      printf("oop!\n");
    else
      printf("%d\n", ans);
  }
}
题目详情
4 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

城堡问题

    1   2   3   4   5   6   7  
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 #   #   |   |   |   |   #   #
   #############################

           (图 1)

   #  = Wall   

   |  = No wall

   -  = No wall

图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成m×n(m≤50,n≤50)个方块,每个方块可以有0~4面墙。

时间限制:1000

内存限制:65536

输入

程序从标准输入设备读入数据。第1、2行每行1个整数,分别是南北向、东西向的方块数。在接下来的输入行里,每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙,1表示西墙,2表示北墙,4表示东墙,8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。

输出

输出2行,每行一个数,表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。

样例输入

4 
7 
11 6 11 6 3 10 6 
7 9 6 13 5 15 5 
1 10 12 7 13 7 5 
13 11 10 8 10 12 13

样例输出

5
9
答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
int maze[60][60],M,N;
int book[60][60];
int roomnum=0,maxroom=0,room;
void dfs(int x,int y){
	if(book[x][y])return;
	room++;
	book[x][y]=1;
	if((maze[x][y]&1)==0)dfs(x,y-1); 
	if((maze[x][y]&2)==0)dfs(x-1,y); 
	if((maze[x][y]&4)==0)dfs(x,y+1); 
	if((maze[x][y]&8)==0)dfs(x+1,y); 
}
int main() {
	cin>>M>>N;
	memset(book,0,sizeof(book));
	for(int i=0;i<M;i++)
	for(int j=0;j<N;j++)
	cin>>maze[i][j]; 
	for(int i=0;i<M;i++)
	for(int j=0;j<N;j++){
		if(!book[i][j]){
			room=0;
			roomnum++;
			dfs(i,j);
			maxroom=maxroom>room?maxroom:room;
		}
	}
	cout<<roomnum<<endl<<maxroom<<endl;
	return 0;
}
题目详情
5 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

红与黑(2023.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;
}


题目详情
6 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

拯救公主(2023.12)

多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。

    身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。

    你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。

    地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。

时间限制:1000

内存限制:65536

输入

第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。

输出

对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。


样例输入

1
7 8 2
........
..S..#0.
.##..1..
.0#.....
...1#...
...##E..
...1....

样例输出

11
答案与解析
参考答案
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
struct POINT {
  int x, y, tot;
  bool get_jewel[7], enchantment;
} point, door;
int main() {
  int k, F[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
  scanf("%d", &k);
  for (int kk = 1; kk <= k; kk++) {

    queue<POINT> que;
    int r, c, needkind, door_coord[15][2] = {}, sdoor_coord = 0;
    char maze[205][205] = {};
    bool walked[205][205][35] = {}, finish = false;
    scanf("%d%d%d", &r, &c, &needkind);
    for (int i = 0; i < r; i++) {
      scanf("%s", maze[i]);
      for (int j = 0; j < c; j++) {
        if (maze[i][j] == 'S') {
          memset(point.get_jewel, false, sizeof(point.get_jewel));
          point.x = i;
          point.y = j;
          point.tot = 0;
          point.enchantment = true;
        }
        if (maze[i][j] == '$') {
          door_coord[sdoor_coord][0] = i;
          door_coord[sdoor_coord++][1] = j;
        }
      }
    }
    que.push(point);
    while (!que.empty()) {
      for (int i = 0; i < 4; i++) {
        point = que.front();
        point.tot++;
        point.x += F[i][0];
        point.y += F[i][1];
        if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
            maze[point.x][point.y] == '#')
          continue;
        if ('0' <= maze[point.x][point.y] && maze[point.x][point.y] <= '4')
          point.get_jewel[maze[point.x][point.y] - '0'] = true;
        int sget_jewel = 0, ss = 0;
        for (int i = 0; i < 5; i++)
          if (point.get_jewel[i])
            sget_jewel += pow(2, i), ss++;
        if (walked[point.x][point.y][sget_jewel])
          continue;
        walked[point.x][point.y][sget_jewel] = true;
        if (ss >= needkind)
          point.enchantment = false;
        if (maze[point.x][point.y] == '$') {
          door = point;
          for (int i = 0; i < sdoor_coord; i++)
            if (door_coord[i][0] != point.x || door_coord[i][1] != point.y) {
              door.x = door_coord[i][0];
              door.y = door_coord[i][1];
              que.push(door);
            }
        }
        if (maze[point.x][point.y] == 'E' && !point.enchantment) {
          printf("%d\n", point.tot);
          finish = true;
        }
        if (finish)
          break;
        que.push(point);
      }
      if (finish)
        break;
      que.pop();
    }
    if (!finish)
      printf("oop!\n");
  }
  return 0;
}
// 参考答案2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define N 210
using namespace std;
int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}};
int dp[N][N][1 << 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans;
char map[N][N];
struct node {
  int x, y, step, key;
  node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){};
};
bool check(int key) {
  int cnt = 0;
  for (int i = 0; i <= 5; i++)
    if ((key >> i) & 1)
      cnt++; // 位运算 统计这条路上可获不同种类的宝石数量
  if (cnt >= k)
    return 1;
  return 0;
}
int bfs(int x, int y) {
  queue<node> que; // 根据结构体 定义队列que
  dp[x][y][0] = 1;
  node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量
  que.push(now);        // 进队
  while (!que.empty()) // 当队列不为空时  .empty()-->若队列为空返回1;
  {
    now = que.front();          // 把队头的值赋给now这个结构体上
    que.pop();                  // 弹出队首
    for (int i = 0; i < 4; i++) // 上下左右四个执行方案
    {
      int xx = now.x + dir[0][i]; // 具体变动
      int yy = now.y + dir[1][i];
      int step = now.step; // 步数
      int key = now.key;   //
      if (xx < 0 || xx >= n || yy < 0 || yy >= m)
        continue; // 判断边界
      if (dp[xx][yy][key])
        continue; // 若在队中 不走
      if (map[xx][yy] == '#')
        continue;                           // 禁区 不走
      if (map[xx][yy] == 'E' && check(key)) // 既到达营救点 且 宝石够数
      {
        return step + 1; // 返回步数 //结束遍历
      }
      if (isdigit(map[xx][yy])) //
      {
        dp[xx][yy][key] = 1;                    // 标记 相当于vis
        key = key | (1 << (map[xx][yy] - '0')); // 记录宝石
        que.push(node(xx, yy, step + 1, key));  // 进队
      }
      if (map[xx][yy] == '.') // 普通地带
      {
        dp[xx][yy][key] = 1; // 标记
        que.push(node(xx, yy, step + 1, key));
      }
      if (map[xx][yy] == '$') // 传送门
      {
        dp[xx][yy][key] = 1;                   // 标记
        que.push(node(xx, yy, step + 1, key)); // 进队
        for (int j = 1; j <= tot; j++)         // 遍历 方案
        {
          xx = trans[j][0], yy = trans[j][1];
          if (!dp[xx][yy][key]) {
            dp[xx][yy][key] = 1;                   // 标记
            que.push(node(xx, yy, step + 1, key)); // 进队
          }
        }
      }
    }
  }
  return -1; // 若遍历完还没返回 就说明没有可行方案
}
main() {
  cin >> T; // 组数
  while (T--) {
    memset(dp, 0, sizeof(dp));
    tot = 0;
    num = 0; // 初始化
    scanf("%d%d%d", &n, &m, &k);
    // cin>>n>>m>>k;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) {
        cin >> map[i][j];
        // scanf("%c",&map[i][j]);还是没搞明白为什么不能用scanf和getchar
        // map[i][j]=getchar();
        if (map[i][j] == 'S')
          x = i, y = j, map[i][j] = '.'; // 标记起点
        if (map[i][j] == '$')
          trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门
        if (isdigit(map[i][j]))
          num++; // 判断是否是宝石(数字)
      }
    if (k > num) {
      printf("oop!\n");
      continue;
    } // 没有足够的宝石
    ans = bfs(x, y);
    if (ans == -1)
      printf("oop!\n");
    else
      printf("%d\n", ans);
  }
}
// 参考答案3
#include <bits/stdc++.h>
using namespace std;
struct Point {
  int x, y, step;     // 坐标 步长
  bool germ[7], ench; // 找到的宝石  结界
} point, door;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int k;
int main() {
  cin >> k;
  while (k--) {
    // 准备工作
    queue<Point> q;
    int r, c, needk; // 边界 需要宝石种类
    cin >> r >> c >> needk;
    int door_c[15][2]{}, door_n = 0; // 传送门坐标 数量
    char ma[205][205]{};             // 地图
    bool walked[205][205][35]{}, finish = false;
    // 标记路是否走过及取得的宝石种类   是否完成
    for (int i = 0; i < r; i++) {
      cin >> ma[i];
      for (int j = 0; j < c; j++) {
        if (ma[i][j] == 'S') { // 起点
          memset(point.germ, false, sizeof(point.germ));
          point.x = i;
          point.y = j;
          point.step = 0;
          point.ench = true;
        }
        if (ma[i][j] == '$') { // 传送门
          door_c[door_n][0] = i;
          door_c[door_n][1] = j;
          door_n++;
        }
      }
    }
    // 广搜
    q.push(point);
    while (!q.empty()) {
      for (int i = 0; i < 4; i++) {
        point = q.front();
        point.step++;
        point.x += dx[i];
        point.y += dy[i];
        if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
            (ma[point.x][point.y] == '#'))
          continue;
        if (ma[point.x][point.y] >= '0' &&
            ma[point.x][point.y] <= '4') // 找到宝石
          point.germ[ma[point.x][point.y] - '0'] = true;
        int get_v = 0, s = 0;
        for (int i = 0; i <= 4; i++) // 统计宝石
          if (point.germ[i]) {
            get_v += (int)pow(2, i);
            s++;
          }
        if (walked[point.x][point.y][get_v])
          continue;                             // 之前到达过
        walked[point.x][point.y][get_v] = true; // 标记
        if (s >= needk)
          point.ench = false;              // 结界消失
        if (ma[point.x][point.y] == '$') { // 找到传送门
          door = point;
          for (int i = 0; i < door_n; i++) // 遍历所有的传送门
            if ((door_c[i][0] != point.x) ||
                (door_c[i][1] != point.y)) { // 可传送
              door.x = door_c[i][0];
              door.y = door_c[i][1];
              q.push(door);
            }
        }
        if (ma[point.x][point.y] == 'E' && !point.ench) { // 找到终点且无结界
          cout << point.step << endl;
          finish = true;
        }
        if (finish)
          break;
        q.push(point);
      }
      if (finish)
        break;
      q.pop();
    }
    if (!finish)
      cout << "oop!" << endl;
  }
  return 0;
}
题目详情
7 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

走出迷宫(2024-3-7级)

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。

时间限制:1000

内存限制:65536

输入

第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。

输出

输出从起点到出口最少需要走的步数。


样例输入

3 3
S#T
.#.
...

样例输出

6
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, m, p[10008], q[10008], ans[108][108], qx, qy, zx, zy;
char a[108][108];
int xx[5] = {0, 1, -1, 0, 0};
int yy[5] = {0, 0, 0, 1, -1};
void bfs() {
  a[qx][qy] = '#';
  ans[qx][qy] = 0;
  int head = 1;
  int tail = 1;
  p[1] = qx;
  q[1] = qy;
  while (head <= tail) {
    for (int i = 1; i <= 4; i++) {
      int h = p[head] + xx[i];
      int l = q[head] + yy[i];
      if (a[h][l] != '#' && h >= 1 && l >= 1 && h <= n && l <= m) {
        a[h][l] = '#';
        tail++;
        p[tail] = h;
        q[tail] = l;
        ans[h][l] = ans[p[head]][q[head]] + 1;
        if (h == zx && l == zy) {
          cout << ans[h][l] << endl;
          return;
        }
      }
    }
    head++;
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      if (a[i][j] == 'S') {
        qx = i;
        qy = j;
      }
      if (a[i][j] == 'T') {
        zx = i;
        zy = j;
      }
    }
  }
  bfs();

  return 0;
}
题目详情
8 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

简单路径

题目描述

给定一个简单无向图,包含 N 个顶点和 M 条边。顶点编号为 1 至 N。每个顶点的度数不超过 10。

定义一条简单路径为顶点序列 v1,v2,…,vk,满足 v1=1,相邻顶点有边相连,且所有顶点互不相同(长度为 0 的路径仅包含顶点 1 本身)。

设所有这样的简单路径的总数为 K。 如果 K>2200,则输出 X;否则输出 K。

输入格式

第一行,两个整数 N,M。

接下来 M 行,每行两个整数 ui,vi,表示一条边。

输出格式

输出一个整数或大写字母 X。

输入样例#1

4 2
1 2
2 3

输出样例#1

3

输入样例#2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例#2

16

输入样例#3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

输出样例#3

2023

说明提示

1≤N≤2×105

0≤M≤min(2×105, 2N(N−1))

1≤ui,vi≤N

图是简单图,每个顶点度数 ≤10

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;


const int LIMIT = 1 << 20;
const int MAXN = 200005;

vector<int> g[MAXN];
bool vis[MAXN];
int ans;

void dfs(int u)
{
    ans++;
    if (ans > LIMIT) return;
    for (int v : g[u])
    {
        if (!vis[v])
        {
            vis[v] = true;
            dfs(v);
            vis[v] = false;
            if (ans > LIMIT) return;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(vis, 0, sizeof(vis));
    ans = 0;
    vis[1] = true;
    dfs(1);
    if (ans > LIMIT)
        cout << "X\n";
    else
        cout << ans << "\n";
    return 0;
}
题目详情
9 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

给定一棵包含 N个顶点的树。顶点编号为 1 至 N,第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。

对于树中任意两个顶点 u 和 v(满足 u<v),定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。

请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。

输入格式

第一行 ,一个整数表示n

接下来的n−1行,每行两个整数ai,bi.

输出格式

输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。


输入样例#1

3
1 2
2 3

输出样例#1

3

输入样例#2

5
1 2
1 3
1 4
1 5

输出样例#2

10

说明提示

【 数据范围 】

2≤N≤105

1≤ai,bi≤N

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案

答案整理中……

题目详情
10 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

工作规划

题目描述

n 台机器人正在完成任务。其中,第 i 台机器人需要工作 ti 分钟才能完成任务。这些机器人之间有一些前后约束,其中约束关系共有m条,每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。

请问,所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的,所有机器人一定在有限时间内完成工作。

输入格式

第一行:两个整数 n 和 m

第二行到第 n+1 行:每个机器人需要的时间 ti

接下来 m 行:每行有两个整数 a 和 b,表示第 b 台机器人必须要等第 a 台机器人任务完成之后才能开始工作。

输出格式

单个整数,表示所有机器人任务完成最少需要花多少时间。


输入样例

10 9
3
29
1
35
18
22
8
29
4
12
3 2
4 8
1 7
6 5
7 10
8 1
10 9
2 4
5 3

输出样例

161

说明提示

1≤n≤104

1≤m≤50,000

1≤ti≤105

1≤ai,bi≤n

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 10005
#define MAX_M 50005
#define INF 0x3f3f3f3f

typedef struct Node {
   int to;
   struct Node* next;
} Node;

Node* adj[MAX_N];  // 邻接表
int in_degree[MAX_N];  // 入度数组
int t[MAX_N];  // 每个机器人的工作时间
int earliest_start[MAX_N];  // 每个机器人的最早开始时间
int n, m;

// 添加边
void add_edge(int u, int v) {
   Node* new_node = (Node*)malloc(sizeof(Node));
   new_node->to = v;
   new_node->next = adj[u];
   adj[u] = new_node;
   in_degree[v]++;
}

// 拓扑排序计算最早完成时间
int topological_sort() {
   int queue[MAX_N];
   int front = 0, rear = 0;

   // 初始化队列,将入度为0的节点加入队列
   for (int i = 1; i <= n; i++) {
       if (in_degree[i] == 0) {
           queue[rear++] = i;
           earliest_start[i] = 0;  // 入度为0的节点最早开始时间为0
       }
   }

   // 处理队列中的节点
   while (front < rear) {
       int u = queue[front++];

       // 遍历所有后继节点
       Node* current = adj[u];
       while (current != NULL) {
           int v = current->to;
           // 更新后继节点的最早开始时间
           if (earliest_start[v] < earliest_start[u] + t[u]) {
               earliest_start[v] = earliest_start[u] + t[u];
           }
           // 减少后继节点的入度
           in_degree[v]--;
           if (in_degree[v] == 0) {
               queue[rear++] = v;
           }
           current = current->next;
       }
   }

   // 计算最大最早完成时间
   int max_time = 0;
   for (int i = 1; i <= n; i++) {
       int finish_time = earliest_start[i] + t[i];
       if (finish_time > max_time) {
           max_time = finish_time;
       }
   }

   return max_time;
}

int main() {
   // 初始化
   memset(adj, 0, sizeof(adj));
   memset(in_degree, 0, sizeof(in_degree));
   memset(earliest_start, 0, sizeof(earliest_start));

   // 读取输入
   scanf("%d %d", &n, &m);
   for (int i = 1; i <= n; i++) {
       scanf("%d", &t[i]);
   }
   for (int i = 0; i < m; i++) {
       int a, b;
       scanf("%d %d", &a, &b);
       add_edge(a, b);
   }

   // 计算并输出结果
   int result = topological_sort();
   printf("%d\n", result);

   // 释放内存
   for (int i = 1; i <= n; i++) {
       Node* current = adj[i];
       while (current != NULL) {
           Node* temp = current;
           current = current->next;
           free(temp);
       }
   }

   return 0;
}
题目详情