T1

用顺序存储实现栈的初始化、入栈、出栈、取栈顶、判栈空操作。调用以上操作实现判断从键盘输入的括号序列是否匹配

输入描述

括导序列#(#为括号输入结束符号)

输出描述

匹配或不匹配

输入

{[()]}#

输出

匹配

#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
class Stack {
private:
    char data[MAX_SIZE];
    int top;
public:
    Stack() {
        top = -1;
    }
    void init() {
        top = -1;
    }
    bool push(char item) {
        if (top == MAX_SIZE - 1) {
            return false;
        }
        data[++top] = item;
        return true;
    }
    char pop() {
        if (top == -1) {
            return '\0';
        }
        return data[top--];
    }
    char peek() {
        if (top == -1) {
            return '\0';
        }
        return data[top];
    }
    bool isEmpty() {
        return top == -1;
    }
};
bool isMatchingBrackets(string input) {
    Stack stack;
    stack.init();
    for (char c : input) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        }
        else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                return false;
            }
        }
        else if (c == '#') {
            break;
        }
    }
    return stack.isEmpty();
}
int main() {
    string input;
    cin >> input;
    if (isMatchingBrackets(input)) {
        cout << "匹配" << endl;
    }
    else {
        cout << "不匹配" << endl;
    }
    return 0;
}

T2

患者到医院看病的顺序是，先排队等候，再看病治疗。要求设计个算法，模拟病人等候就诊的过程。其中：“病人到达"用命令“A”(或"a")表示，"护士让下一位就诊”用"N”(或"n")表示，“不再接收病人排队"用“S”(或“s”)表示,

输入描述

A(或a)病历号

N(或n)

S(或s)

X（其他字符）

输出描述

病历号为x的病人就诊

若队列中有数据，输出队首元素，否则输出“无病人就诊”

不再接收病人排队，并输出当前队列中所有病历号

输入命令不合法！

输入

A

123

n

n

a

124

A

125

X

S

输出

病历号为123的病人就诊

无病人就诊

输入命令不合法!

今天不再接收病人排队，下列排队的病人依次就诊：124 125

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_SIZE = 100;
class PatientQueue {
private:
    int data[MAX_SIZE];
    int front;
    int rear;
public:
    PatientQueue() {
        front = rear = -1;
    }
    bool isEmpty() {
        return front == -1;
    }
    bool isFull() {
        return (rear + 1) % MAX_SIZE == front;
    }
    void enqueue(int patientNumber) {
        if (isFull()) {
            cout << "队列已满，无法加入新病人。" << endl;
            return;
        }
        if (isEmpty()) {
            front = rear = 0;
        }
        else {
            rear = (rear + 1) % MAX_SIZE;
        }
        data[rear] = patientNumber;
    }
    int dequeue() {
        if (isEmpty()) {
            cout << "无病人就诊" << endl;
            return -1;
        }
        int patientNumber = data[front];
        if (front == rear) {
            front = rear = -1;
        }
        else {
            front = (front + 1) % MAX_SIZE;
        }
        return patientNumber;
    }
    void printQueue() {
        if (isEmpty()) {
            cout << "当前队列中无病人。" << endl;
            return;
        }
        cout << "今天不再接收病人排队，下列排队的病人依次就诊：";
        int index = front;
        while (index != rear) {
            cout << data[index] << " ";
            index = (index + 1) % MAX_SIZE;
        }
        cout << data[index] << endl;
    }
};
int main() {
    PatientQueue queue;
    char command;
    int patientNumber;
    while (true) {
        cin >> command;
        if (command == 'A' || command == 'a') {
            cin >> patientNumber;
            queue.enqueue(patientNumber);
        }
        else if (command == 'N' || command == 'n') {
            int patient = queue.dequeue();
            if (patient != -1) {
                cout << "病历号为" << patient << "的病人就诊" << endl;
            }
        }
        else if (command == 'S' || command == 's') {
            queue.printQueue();
            break;
        }
        else {
            cout << "输入命令不合法！" << endl;
        }
    }
    return 0;
}

T3

迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径

输入描述

迷宫宽度W 迷宫高度h

迷宫第一行

迷宫第二行

…

迷宫第n行

输出描述

入口横坐标1 入口纵坐标1

横坐标2 纵坐标2

横坐标3 纵坐标3

横坐标4 纵坐标4

横坐标n-1 纵坐标n-1

…

出口横坐标n 出口纵坐标n

输入

8 10

1 1 1 1 1 1 1 1

1 0 1 1 0 1 0 1

1 0 1 0 0 1 0 1

1 1 0 3 1 0 1 1

1 0 0 1 0 0 4 1

1 0 0 0 0 1 1 1

1 0 1 0 0 1 0 1

1 0 1 0 0 0 1 1

1 1 1 1 0 0 0 1

1 1 1 1 1 1 1 1

输出

3 3

2 3

2 4

2 5

3 5

3 6

3 7

4 7

4 6

4 5

4 4

5 4

6 4

#include <iostream>
#include <list>
using namespace std;

struct PosInfo {
    int px, py;
    PosInfo(int x, int y) { px = x; py = y; }
};

class MG {
    char** S;
    int w, h;
    int in_x, in_y, out_x, out_y;
    list<PosInfo> s;

public:
    MG(int w, int h) {
        this->w = w;
        this->h = h;
        this->S = new char* [h];
        for (int i = 0; i < h; i++) {
            this->S[i] = new char[w];
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> S[i][j];
                if (S[i][j] == '3') {
                    in_y = j;
                    in_x = i;
                }
                if (S[i][j] == '4') {
                    out_x = i;
                    out_y = j;
                }
            }
        }
        seekPath(in_x, in_y); 
    }

    bool could(int x, int y)
    {
        return (S[x][y] != '*' && S[x][y] != '1');
    }

    bool seekPath(int x, int y) {

        s.push_front(PosInfo(y, x));
        if (x == out_x && y == out_y) {
            if (s.empty()) { cout << "列表为空" << endl; return false; }
            while (!s.empty()) {
                cout << s.back().px << " " << s.back().py << endl;
                s.pop_back();
            }
            return true;
        }
        if (could(x, y)) {
            S[x][y] = '1';
            if (seekPath(x + 1, y)) return true;
            if (seekPath(x, y - 1)) return true;
            if (seekPath(x - 1, y)) return true;
            if (seekPath(x, y + 1)) return true;
        }

        s.pop_front();
        return false;
    }

    ~MG() {
        for (int i = 0; i < h; i++) {
            delete[] S[i];
        }
        delete[] S;
    }
};

int main() {
    int w, h;
    cin >> w >> h;
    MG m1(w, h);
    return 0;
}

T4

设计一个算法找一条从迷宫入口到出口的最短路径

输入描述

迷宫的行和列m n

迷宫的布局

输出描述

最小路径

输入

6 8

0 1 1 1 0 1 1 1

1 0 1 0 1 0 1 0

0 1 0 0 1 1 1 1

0 1 1 1 0 0 1 1

1 0 0 1 1 0 0 0

0 1 1 0 0 1 1 0

输出

(6,8)

(5,7)

(4,6)

(4,5)

(3,4)

(3,3)

(2,2)

(1,1)

#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

class MG {
    int m, n;
    int** S;
    vector<Point> path; 
    vector<vector<bool>> visited; 

public:
    MG(int m, int n) {
        this->m = m;
        this->n = n;
        S = new int* [m];
        for (int i = 0; i < m; i++) {
            S[i] = new int[n];
        }


        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> S[i][j];
            }
        }

        visited.resize(m, vector<bool>(n, false));
        searchPath();
        printPath();
    }
    bool could(int x, int y) {
        return (x >= 0 && x < m && y >= 0 && y < n && S[x][y] == 0 && !visited[x][y]);
    }
    void searchPath() {
        queue<pair<Point, vector<Point>>> q;
        q.push({ Point(0, 0), {Point(0, 0)} });
        visited[0][0] = true;

        vector<pair<int, int>> directions = {
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, -1}, {-1, 1} 
        };

        while (!q.empty()) {
            auto current = q.front();
            q.pop();
            Point point = current.first;
            vector<Point> currentPath = current.second;
            if (point.x == m - 1 && point.y == n - 1) {
                path = currentPath; 
                return;
            }
            for (auto dir : directions) {
                int newX = point.x + dir.first;
                int newY = point.y + dir.second;

                if (could(newX, newY)) {
                    visited[newX][newY] = true;
                    vector<Point> newPath = currentPath;
                    newPath.push_back(Point(newX, newY));
                    q.push({ Point(newX, newY), newPath });
                }
            }
        }
    }

    void printPath() {
        for (int i = path.size() - 1; i >= 0; --i) {
            cout << "(" << path[i].x + 1 << "," << path[i].y + 1 << ") " << endl;
        }
    }

    ~MG() {
        for (int i = 0; i < m; i++) {
            delete[] S[i];
        }
        delete[] S;
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    MG m1(m, n);
    return 0;
}