题目

小江最喜欢玩的游戏”天下3”最近推出了连连看的小玩法。玩家可以将2个相同图案的牌子连接起来，连接线不多于3根线段（即最多拐2折），就可以成功将这对牌子消除。如示意图所示，红色，黄色和蓝色的消除都是合法的，因为它们分别需要2个，0个和1个折。而黑色的消除是不合法的，因为这对牌至少需要拐3个折才能连接起来。

但是小江并不满足于这个游戏规则，因为他觉得最多只能拐2折这个限制并不合理。好奇的小江想知道的是，给定一个连连看的状态以及某一个牌子，在K折以内可以到达的所有具有相同图案的牌子的数量是多少。

输入

每个输入数据包含多个测试点。

第一行为测试点的个数S <= 20。之后是S个测试点的数据。

每个测试点的第一行为1 <= N <= 200, 1 <= M <= 200，表示连连看的大小。接下来的N行，每一行有M个整数，表示连连看该行的状态，如果为0，则表示该格为空，否则代表一种图案的牌子。

然后是三个整数X <= N, Y <= M，0 <= K <= 10000，表示查询(X, Y)这个牌子在K折以内能消除的所有相同牌子总数。其中连连看左上角的格子坐标为(1, 1)，右下角为(N, M)。保证查询的格子是有图案的。

输出

对于每个测试点，输出对应的能消除的所有牌子总数。

提示

样例第一个例子，第(1, 1), (2, 3)和(2, 5)为3个可以在3折内被消除的相同牌子。

样例

输入34 51 0 1 0 20 0 1 3 13 3 1 5 96 1 4 8 71 3 34 51 0 1 0 20 0 1 3 13 3 1 5 96 1 4 8 71 3 12 21 102 31 1 10输出320

分析

这题使用广搜的思想来做。

我们使用如下的数据结构表示一个搜索状态

struct State {int x, y;//坐标int num; //已转折次数int cx, cy; //方向}

对当前的状态，我们往跟原方向不在一条线上的两个方向发散（初始时往4个方向发散），直到遇到不为0或者不合法的坐标为止。将为0且未访问过的坐标用一个状态保存起来并压入队列。将所有已访问的坐标标记一下。记录下在转折次数不超过K时遇到的目标点的个数即为答案。

代码

#include <iostream>#include <queue>#include <string.h>using namespace std;struct State {int x, y;int num;int cx, cy;State() {}State(int ox, int oy, int onum, int ocx, int ocy) {x = ox; y = oy;num = onum;cx = ocx; cy = ocy;}};const int CX[] = {1, 0, -1, 0};const int CY[] = {0, 1, 0, -1};int Map[202][202];bool vis[202][202];int T, N, M, X, Y, K;//检查是否出界bool valid(int x, int y){return x >=0 && x <= N + 1 && y >= 0 && y <= M + 1;}int main() {scanf("%d", &T);while (T--) {memset(Map, 0, sizeof(Map));memset(vis, false, sizeof(vis));scanf("%d%d", &N, &M);for (int i = 1; i <= N; ++i)for (int j = 1; j <= M; ++j)scanf("%d", &Map[i][j]);scanf("%d%d%d", &X, &Y, &K);int count = 0;vis[X][Y] = true;queue<State> que;for (int i = 0; i < 4; i++){int nx = X, ny = Y;while (true){nx += CX[i];ny += CY[i];if (!valid(nx, ny)) break;if (Map[nx][ny] == 0){if (!vis[nx][ny])que.push(State(nx, ny, 0, CX[i], CY[i]));vis[nx][ny] = true;continue;}if (Map[nx][ny] == Map[X][Y] && !vis[nx][ny]){count++;}vis[nx][ny] = true;break;}}while (!que.empty()){State cur = que.front();que.pop();if (cur.num == K) continue;for (int i = 0; i < 4; i++){//同方向跳过if (CX[i] == cur.cx && CY[i] == cur.cy) continue;if (CX[i] + cur.cx == 0 && cur.cy + CY[i] == 0) continue;int nx = cur.x, ny = cur.y;while (true){nx += CX[i];ny += CY[i];if (!valid(nx, ny)) break;if (Map[nx][ny] == 0){if (!vis[nx][ny])que.push(State(nx, ny, cur.num + 1, CX[i], CY[i]));vis[nx][ny] = true;continue;}if (Map[nx][ny] == Map[X][Y] && !vis[nx][ny]){count++;}vis[nx][ny] = true;break;}}}printf("%d\n", count);}return 0;}