---
# System prepended metadata

title: ý tưởng tương tự với bài https

---

Coi  ma trận là một đồ thị có $n \times m$ đỉnh thì ta có:
Mỗi đỉnh $(i,j)$ sẽ có cạnh nối với các đỉnh $(i+1,j)$, $(i,j+1)$, $(i,j-1)$,$(i-1,j)$.

Sau đấy ta sẽ dùng thuật toán BFS.

:::spoiler Code mẫu(c++)
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 1;

int n, m;
bool blocked[maxn][maxn]; // đã thăm ô này hoặc ban đầu có bị chặn chưa
int dx[] = {-1, 0, 1,  0}; // chuẩn bị mảng để duyệt 4 ô xung quanh
int dy[] = { 0, 1, 0, -1};
int d[maxn][maxn]; // khoảng cách bé nhất để đi tới ô (i,j)

bool valid(int vx, int vy) {  // kiểm tra có đi được vào ô (vx,vy) không
	return !blocked[vx][vy] && 1 <= vx && vx <= n && 1 <= vy && vy <= m;
}

void bfs(int rx, int ry) { // cài đặt bfs
	deque<pair<int, int> > q;	q.push_back(make_pair(rx, ry));
	blocked[rx][ry] = true;
	d[rx][ry] = 0;

	while (q.size()) {
		pair<int, int> u = q.front();	q.pop_front();
		int ux = u.first, uy = u.second;

		for (int i = 0; i < 4; ++i) {
			int vx = ux + dx[i], vy = uy + dy[i];
			if (valid(vx, vy)) {
				q.push_back(make_pair(vx, vy));
				blocked[vx][vy] = true;
				d[vx][vy] = d[ux][uy] + 1; 
				if (vx == n && vy == m) return;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			char x;	cin >> x;
			blocked[i][j] = x - '0';
		}
	}
	bfs(1, 1);
	cout << d[n][m];
	return 0;
}
```

:::