路径规划

题目描述

$hhj$ 发现自己其实是纸片人！他意识到自己居住在一个二维平面中，平面里有一个 $N\times N$ 的矩阵（$2\le N \le 100$）。他可以沿着上下左右四个方向穿过矩阵中的每个格子，但始终无法离开矩阵（惨）。

他肆意地在矩阵中游荡，直到发现前路难行——原来，有人在画图时将某些相邻格子间的线条描得太粗，致使 $hhj$ 必须付出更多努力才能突破这一间隔。当然，$hhj$ 并不想走得如此艰辛，他决定提前规划好前进的路线。

$hhj$ 决定只经过 $K$ 个格子（$1\le K \le 100, K \le N^{2}$）。如果两个格子间必须越过至少一条粗线才能到达，则定义两个格子是“难走的”。

请帮助他计算出在即将经过的 $K$ 个格子中，有多少对格子是“难走的”。

输入格式

第一行输入包含 $N$， $K$和 $M$，分别表示矩阵大小、要经过的格子数量和粗线的数量。

接下来的 $M$ 行描述了两个由粗线隔开的格子，格式为 $r\ c\ r'\ c'$（都是在 $1...N$中的整数），表示第 $r$ 行第 $c$ 列和第 $r'$ 行第 $c'$ 列之间用粗线隔开了。

最后的 $K$ 行表示即将经过的 $K$ 个格子的行列信息。

输出格式

输出“难走的”格子对的数量。

样例 #1

样例输入 #1

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

样例输出 #1

2

提示

样例解释

样例图示如下，红线表示粗线。

有 $(3,3)$ 和 $(2,3)$，$(3,3)$ 和 $(2,2)$ 两对格子必须通过粗线才能到达。

我的代码：

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int N, K, M;
	cin >> N >> K >> M;

	vector<vector<int> > matrix(N, vector<int>(N, 0));

	// 标记粗线的位置
	for (int i = 0; i < M; i++)
	{
		int r, c, r1, c1;
		cin >> r >> c >> r1 >> c1;
		matrix[r - 1][c - 1] = 1;
		matrix[r1 - 1][c1 - 1] = 1;
	}

	int count = 0;

	// 判断每对格子是否难走
	for (int i = 0; i < K; i++)
	{
		int r, c;
		cin >> r >> c;

		// 检查上方格子
		if (r > 1 && matrix[r - 1][c - 1] == 1 && matrix[r - 2][c - 1] == 1)
		{
			count++;
		}

		// 检查下方格子
		if (r < N && matrix[r - 1][c - 1] == 1 && matrix[r][c - 1] == 1)
		{
			count++;
		}

		// 检查左边格子
		if (c > 1 && matrix[r - 1][c - 1] == 1 && matrix[r - 1][c - 2] == 1)
		{
			count++;
		}

		// 检查右边格子
		if (c < N && matrix[r - 1][c - 1] == 1 && matrix[r - 1][c] == 1)
		{
			count++;
		}
	}

	cout << count/3 << endl;

	return 0;
}

是思路错了吗，为什么不对，只A一个点