算法题：最少转弯问题(turn)

问题描述

给出一张地图，这张地图被分为n×m（n,m≤100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的(x~1~,y~1~)这块平地，问：你至少需要拐几个弯才能到达目的地(x~2~,y~2~)？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。例如：如图，最少的拐弯次数为5。

输入格式

第1行：n,m
第2至n+1行：整个地图地形描述（0：空地；1：高山），
如（图1）第2行地形描述为：1 0 0 0 0 1 0
第3行地形描述为：0 0 1 0 1 0 0
……
第n+2行：x~1~ y~1~ x~2~ y~2~ （分别为起点、终点坐标）

输出格式

s （即最少的拐弯次数）

样例

输入

5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7

输出

5

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <queue>

using namespace std;

struct Point {
    int x, y;
    int ans = 0;
};

int main() {
    int n, m;
    int arr[105][105];
    int x1, y1, x2, y2;

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> arr[i][j];
        }
    }
    cin >> x1 >> y1 >> x2 >> y2;

    // 起点就是终点
    if (x1 == x2 && x2 == y2) {
        cout << 0;
        return 0;
    }

    static int vis[105][105];
    queue<Point> q;
    Point point;
    point.x = x1;
    point.y = y1;
    q.push(point);

    while (!q.empty()) {
        point = q.front();
        q.pop();

        if (point.x == x2 && point.y == y2)
            break;

        //向上走
        for (int i = 0; point.x - i >= 1; ++i) {
            int xx = point.x - i;
            int yy = point.y;

            //有墙走不动了
            if (arr[xx][yy] == 1)
                break;

            if (vis[xx][yy] == 0) {
                vis[xx][yy] = 1;
                Point p;
                p.x = xx;
                p.y = yy;
                p.ans = point.ans + 1;
                q.push(p);
            }
        }

        //向下走
        for (int i = 0; point.x + i <= n; ++i) {
            int xx = point.x + i;
            int yy = point.y;

            //有墙走不动了
            if (arr[xx][yy] == 1)
                break;

            if (vis[xx][yy] == 0) {
                vis[xx][yy] = 1;
                Point p;
                p.x = xx;
                p.y = yy;
                p.ans = point.ans + 1;
                q.push(p);
            }
        }

        //向左走
        for (int i = 0; point.y - i >= 1; ++i) {
            int xx = point.x;
            int yy = point.y - i;

            //有墙走不动了
            if (arr[xx][yy] == 1)
                break;

            if (vis[xx][yy] == 0) {
                vis[xx][yy] = 1;
                Point p;
                p.x = xx;
                p.y = yy;
                p.ans = point.ans + 1;
                q.push(p);
            }
        }

        //向右走
        for (int i = 0; point.y + i <= m; ++i) {
            int xx = point.x;
            int yy = point.y + i;

            //有墙走不动了
            if (arr[xx][yy] == 1)
                break;

            if (vis[xx][yy] == 0) {
                vis[xx][yy] = 1;
                Point p;
                p.x = xx;
                p.y = yy;
                p.ans = point.ans + 1;
                q.push(p);
            }
        }
    }

    cout << point.ans - 1;

    return 0;
}