# 12202: 【原2202】梅西的过人

### 题目描述

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

m 0 1 0
0 0 1 0
1 0 1 d

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

Sample output 1:
1

# 数据范围：

``````对50%的数据  3<=N,m<=100

``````

## 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;
}
``````