# ZeroJudge - d821: 最短路徑個數
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d821
###### tags: `ZeroJudge` `廣度優先搜尋（Breadth First Search）` `動態規劃（Dynamic Programming）`

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define MOD 100000

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int rows, columns, startX, startY, endX, endY, newX, newY, dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 }, DP[52][52];
	bool blocked[52][52], walked[52][52];
	while (cin >> rows >> columns) {
		memset(blocked, true, sizeof(blocked));
		for (int i = 1; i <= rows; ++i)
			for (int j = 1; j <= columns; ++j)
				cin >> blocked[i][j];
		cin >> startY >> startX >> endY >> endX;
		++startX; ++startY; ++endX; ++endY;
		queue <int> Qx, Qy;
		Qx.push(startX); Qy.push(startY);
		memset(DP, 0, sizeof(DP)); DP[startY][startX] = !blocked[startY][startX];
		memset(walked, false, sizeof(walked)); walked[startY][startX] = true;
		while (!Qx.empty()) {
			startX = Qx.front(); Qx.pop();
			startY = Qy.front(); Qy.pop();
			for (int i = 0; i < 4; ++i) {
				newX = startX + dx[i]; newY = startY + dy[i];
				DP[startY][startX] += DP[newY][newX];
				if (DP[startY][startX] >= MOD)
					DP[startY][startX] -= MOD;
				if (!blocked[newY][newX] && !walked[newY][newX]) {
					walked[newY][newX] = true;
					Qx.push(newX); Qy.push(newY);
				}
			}
		}
		cout << DP[endY][endX] << '\n';
	}
}