算法题：营救(save)

问题描述

铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。
通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n×n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。
为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。

输入格式

第一行为n，下面是一个n×n的0、1矩阵，表示海洋地图
最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。

输出格式

哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。

样例

输入

3
001
101
100
1 1 3 3

输出

4

数据范围

N≤1000

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <queue>

using namespace std;

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


int n;
bool arr[1005][1005];
bool vis[1005][1005];

bool check(int x, int y) {

    return x >= 1 && y >= 1 && x <= n && y <= n && arr[x][y] == 0 && vis[x][y] == 0;
}

int main() {

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            char t;
            cin >> t;
            arr[i][j] = (t == '1');
        }
    }

    point start, end;
    cin >> start.x >> start.y;
    cin >> end.x >> end.y;

    queue<point> q;
    q.push(start);

    int ans = 0;
    while (!q.empty()) {
        point t = q.front();
        q.pop();

        if (t.x == end.x && t.y == end.y) {
            ans = t.ans;
            break;
        }

        if (check(t.x - 1, t.y)) {
            point tt;
            tt.x = t.x - 1;
            tt.y = t.y;
            tt.ans = t.ans + 1;

            vis[tt.x][tt.y] = 1;
            q.push(tt);
        }

        if (check(t.x, t.y - 1)) {
            point tt;
            tt.x = t.x;
            tt.y = t.y - 1;
            tt.ans = t.ans + 1;

            vis[tt.x][tt.y] = 1;
            q.push(tt);
        }

        if (check(t.x + 1, t.y)) {
            point tt;
            tt.x = t.x + 1;
            tt.y = t.y;
            tt.ans = t.ans + 1;

            vis[tt.x][tt.y] = 1;
            q.push(tt);
        }

        if (check(t.x, t.y + 1)) {
            point tt;
            tt.x = t.x;
            tt.y = t.y + 1;
            tt.ans = t.ans + 1;

            vis[tt.x][tt.y] = 1;
            q.push(tt);
        }
    }

    cout << ans;

    return 0;
}