12202: 【原2202】梅西的过人

题目描述

author: cloudygoose 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2202

题目描述

梅西来SJTU了！这让交大学子沸腾了，为了体现阿根廷和中国的国际友谊，校长决定让梅西与电院组织一场友谊赛。这场比赛在南体进行，把南体分成一个n乘m的矩阵，一开始梅西在(1,1)位置，球门在(n,m)位置，只要梅西能带球到球门处就算梅西胜利。电院几乎派出了所有学生来阻挡梅西，但是因为梅西的气场，他们站在场上都不敢动。如下图，是一个3乘4的球场，每个位置上的数字表示这个位置有没有站电院的学生。m是梅西，d是球门。
m 0 1 0
0 0 1 0
1 0 1 d
同时，为了公平起见，限定梅西只能过一个人，就是说梅西能跨入“1”的格子，但只能进入一次。同时规定梅西只能四方向移动，就是说梅西不能从一个格子走到它右上角的格子。在上面的这个例子中，梅西能通过过一个人来走到球门处。
m 1 0 0
1 1 1 1
0 0 1 d
但在这个例子中，梅西就到不了了，因为他必须过两个人。
在球场上没有时间给你思考！只有一秒钟时间在决定能否到球门处。

输入

k组数据，给出n，m，分别是矩阵的行数和列数，之后给出n行，每行m个数，每个数是0或者1，在(1，1)和(n,m)必是0。表示在这个位置上是否有电院的学生。
Sample input 1:
1
3 4
0 0 1 0
0 0 1 0
1 0 1 0

输出

输出k行，给出梅西是否能到达球门，1表示能，0表示不能。
Sample output 1:
1

数据范围：

对50%的数据  3<=N,m<=100
对100%的数据 3<=N,m<=1000，k<=4

victrid's solution

#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

inline bool valid_messi(int** mat, int n1, int m1, int n, int m) {
    return n1 < n && n1 >= 0 && m1 < m && m1 >= 0 && (mat[n1][m1] == 0 || mat[n1][m1] == 1);
}
inline bool valid_door(int** mat, int n1, int m1, int n, int m) {
    return n1 < n && n1 >= 0 && m1 < m && m1 >= 0 && (mat[n1][m1] == 0 || mat[n1][m1] == 1 || mat[n1][m1] == 3);
}
bool check() {
    int n, m;
    cin >> n >> m;
    int** inputmat = new int*[n];
    for (int i = 0; i < n; i++) {
        inputmat[i] = new int[m]();
        for (int j = 0; j < m; j++)
            cin >> inputmat[i][j];
    }
    stack<int> lll;
    stack<int> rrr;
    lll.push(0);
    rrr.push(0);
    while (!lll.empty()) {
        int n0 = lll.top();
        int m0 = rrr.top();
        lll.pop();
        rrr.pop();
        if (n0 == n - 1 && m0 == m - 1)
            return true;
        if (inputmat[n0][m0] == 0) {
            if (valid_messi(inputmat, n0 + 1, m0, n, m)) {
                lll.push(n0 + 1);
                rrr.push(m0);
            }
            if (valid_messi(inputmat, n0, m0 + 1, n, m)) {
                lll.push(n0);
                rrr.push(m0 + 1);
            }
            if (valid_messi(inputmat, n0, m0 - 1, n, m)) {
                lll.push(n0);
                rrr.push(m0 - 1);
            }
            if (valid_messi(inputmat, n0 - 1, m0, n, m)) {
                lll.push(n0 - 1);
                rrr.push(m0);
            }
            inputmat[n0][m0] = 2;
        }
        if (inputmat[n0][m0] == 1) {
            inputmat[n0][m0] = 3;
        }
    }
    lll.push(n - 1);
    rrr.push(m - 1);
    while (!lll.empty()) {
        int n0 = lll.top();
        int m0 = rrr.top();
        lll.pop();
        rrr.pop();
        if (inputmat[n0][m0] == 3)
            return true;
        if (inputmat[n0][m0] == 0) {
            if (valid_door(inputmat, n0 + 1, m0, n, m)) {
                lll.push(n0 + 1);
                rrr.push(m0);
            }
            if (valid_door(inputmat, n0, m0 + 1, n, m)) {
                lll.push(n0);
                rrr.push(m0 + 1);
            }
            if (valid_door(inputmat, n0, m0 - 1, n, m)) {
                lll.push(n0);
                rrr.push(m0 - 1);
            }
            if (valid_door(inputmat, n0 - 1, m0, n, m)) {
                lll.push(n0 - 1);
                rrr.push(m0);
            }
            inputmat[n0][m0] = 4;
        }
        if (inputmat[n0][m0] == 1) {
            inputmat[n0][m0] = 5;
        }
    }
    return false;
}
int main() {
    int totalis;
    int* ii = new int[totalis];
    cin >> totalis;
    for (int i = 0; i < totalis; i++) {
        ii[i] = check();
    }
    for (int i = 0; i < totalis; i++) {
        if (i)
            cout << endl;
        cout << to_string(ii[i]);
    }
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int movement[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAX_N = 1000;
struct posdata {
    posdata(int a, int b, bool p) {
        x = a; y = b; cross = p;
    };
    int x, y;
    bool cross = false;
};
int a[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

int main() {

    int k; cin >> k;
    while (k--) {

        int n, m;
        cin >> n >> m;
        memset(a, 0, sizeof(a));
        memset(visited, false, sizeof(visited));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> a[i][j];
        bool found = false;
        queue<posdata> que; while(!que.empty()) que.pop();
        que.push(posdata(0, 0, false)); visited[0][0] = true;

        while (!que.empty()) {

            posdata now = que.front();

            for (int i = 0; i < 4; ++i) {
                posdata next(now.x + movement[i][0], now.y + movement[i][1], now.cross);
                if (next.x < 0 || next.x >= n || next.y < 0 || next.y >= m) continue;
                if (next.x == n - 1 && next.y == m - 1) {
                    found = true;
                    break;
                }
                switch (a[next.x][next.y]) {
                    case 0:
                        if (!visited[next.x][next.y]) {
                            que.push(next);
                            visited[next.x][next.y] = true;
                        }
                        break;
                    case 1:
                        if (!next.cross) {
                            next.cross = true;
                            que.push(next);
                            visited[next.x][next.y] = true;
                        }
                        break;
                }
            }
            if (found) break;
            que.pop();
        }
        if (found) cout << 1 << endl; else cout << 0 << endl;
    }
    return 0;
}