描述

给定一个二维网格和起点、终点坐标，以及允许的最大转弯次数，计算从起点到终点的最短路径。如果无法到达，则输出"no"。

输入描述:

输入包含多组测试数据。

每组数据占一行，包含两个整数 N 和 K，分别表示网格的大小和最大转弯次数。

输出描述:

每组数据输出一行结果，表示是否能找到路径。如果找到路径，输出"yes"；否则输出"no"。

输入示例

5 17

输出示例

yes

代码实现

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Point {
    int x, y;
    int direction; // 方向：1为右，2为左，3为下，4为上
    int turns; // 已经转弯的次数
    Point(int _x, int _y, int _dir, int _turns) : x(_x), y(_y), direction(_dir), turns(_turns) {}
};

bool operator<(const Point& a, const Point& b) {
    return a.turns > b.turns;
}

char grid[200][200];
int visited[101][101][5];

int main() {
    int test_cases;
    cin >> test_cases;

    while (test_cases--) {
        int rows, cols;
        cin >> rows >> cols;
        
        for (int i = 0; i < rows; ++i) {
            cin >> grid[i];
        }

        int max_turns, startX, startY, endX, endY;
        cin >> max_turns >> startY >> startX >> endY >> endX;
        
        --startX; --endX; --startY; --endY;

        memset(visited, 0x3f, sizeof(visited)); // 初始化为极大值

        priority_queue<Point> pq;
        pq.push(Point(startX, startY, 0, 0));

        bool found = false;
        while (!pq.empty()) {
            Point current = pq.top();
            pq.pop();

            if (current.x == endX && current.y == endY) {
                found = true;
                break;
            }

            for (int dir = 1; dir <= 4; ++dir) {
                int nextTurns = (current.direction == dir) ? current.turns : current.turns + 1;
                int newX = current.x, newY = current.y;

                switch (dir) {
                    case 1: ++newX; break; // 向右
                    case 2: --newX; break; // 向左
                    case 3: ++newY; break; // 向下
                    case 4: --newY; break; // 向上
                }

                if (nextTurns <= max_turns && newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
                    grid[newX][newY] != '*' && visited[newX][newY][dir] > nextTurns) {
                    visited[newX][newY][dir] = nextTurns;
                    pq.push(Point(newX, newY, dir, nextTurns));
                }
            }
        }

        if (found) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}