By

文章目录

##题目
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

###描述
《一起消消毒》是网易推出的一款创新的消除类游戏。游戏的基本规则很简单，玩家每次操作可以选择把游戏中相邻的两个图形（垂直相邻或者水平相邻）进行交换，如果交换后，出现三个或三个以上的连续相同图形在一条线上，则视这次操作为一次有效的操作，并且这些相同图形会消失。图形消失后，在同一条垂直线上的图形会往下掉。然后继续把同一直线上大于等于三个的相同图形消除，直到已无可消除的图形，则这次操作结束。

如下图所示，假设左上角坐标为(0,0)，右下角坐标为(8,6)，则交换坐标为（2,0）和(3,0)的操作是一个有效的操作，该操作将使得(0,1),(1,1)和(2,1)的红色图形在同一条线上。同理，交换坐标为(7,5)和(8,5)的操作也是一个有效的操作，在同一线上的三个蓝色图形将消失。

一次操作的完整流程是：

（1）玩家进行交换操作；

（2）得到交换图形的后的局面；

（3）计算在当前局面下所有可以进行消除的图形，注意一次操作有可能使得不止一组图形在同一条线上；

（4）在（3）中计算得到的所有图形同时消失，然后有图形消失了的列，其余剩下的图形往下掉，得到新的局面；

（5）重复执行（3），直到已无图形可以消除。

给出一个局面，同时给出玩家的一次有效的交换操作，请计算出这次操作总共能消除多少个图形。

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

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

每个测试点的第一行为N, M (1 <= N, M <= 20)，之后N行，每行包含M个字符，每个字符代表一个图形，’.’表示该位置为空，’A’…’Z’分别表示一种图案。除此以外局面中无其他字符。之后一行是4个整数x0, y0, x1, y1，表示玩家希望交换的两个相邻图形的坐标位置(x0, y0)以及(x1, y1)。

保证初始的局面为合法局面，无三个或以上连续相同图形在同一线上。并且无悬空的空格，即’.’只会出现在每一列的顶部。

###输出
对于每个测试点，对应的结果输出一行，表示进行交换操作后能消除多少个图形。

###样例输入

1
2
3
4
5
6
7
8
9
10
11
2
4 5
.D.M.
.DCAE
.AABA
MDDAM
2 3 2 4
2 4
F.Z.
ZZAZ
1 2 0 2

###样例输出

1
2
8
4

##我的解答

考试的时候因为时间不够没做出来；
后来想了想大概的思路如下：
1）存储一个整个局面的flag数组，标志是否需要消除；
2）对于每个点，可以横向和纵向查找是否存在3个以上的可以消除，存在则更新flag数组
3）对于第一次交换，只需要考虑交换发生的两个点，因为题目保证初始局面合法；
4）找到所有需要消除的点之后，逐列遍历局面，消除该点，并且将上方的点下降；
5）循环以上过程直到找不到可消除的点；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>

using namespace std;

//对于i所在的行和j所在的列进行遍历，标记可以消除的点
void markBoards(vector<string>& board, vector<vector<bool>>& flag, int i, int j) { 
  int n = board.size();
  int m = board[0].size();
  int a1 = i, a2 = i;
  int temp = 0;
  //纵向扩展
  while ((--a1) >= 0 && board[a1][j] == board[i][j]) temp++;
  while ((++a2) < n && board[a2][j] == board[i][j]) temp++;
  if (temp > 1) {
    for (int k = a1+1; k < a2; ++k) {
      flag[k][j] = true;
    }
  }
  
  a1 = j; a2 = j;
  temp = 0;
  //横向扩展
  while ((--a1) >= 0 && board[i][a1] == board[i][j]) temp++;
  while ((++a2) < m && board[i][a2] == board[i][j]) temp++;
  if (temp > 1) {
    for (int k = a1+1; k < a2; ++k) {
      flag[i][k] = true;
    }
  }
}

//遍历整个局面，计算消除个数，并消除方块，垂直下降，返回消除个数
//逐列遍历，先考虑连续的消除以避免重复的下降
//记得将flag重置
int EliminateAndCount(vector<string>& board, vector<vector<bool>>& flag) {
  int n = board.size();
  int m = board[0].size();
  int a, b;
  int count = 0;
  for (int j = 0; j < m; ++j) {
    for (int i = 0; i < n; ++i) {
      if (board[i][j] != '.') {
        if (flag[i][j] == true) {
          count++;
          a = i; b = i;
          while ((++b) < n && flag[b][j]) {
            count++;
          }
          //下降过程
          for (int k = a-1; k >= 0; --k) {
            board[k+b-a][j] = board[k][j];
            flag[k+b-a][j] = false;
          }
          for (int k = 0; k < b-a; ++k) {
            board[k][j] = '.';
            //flag[k][j] = false;
          }
          i = b+1;
        }
      }
    }
  }
  return count;
}

//简单粗暴的方法
int iterEliminateGame(vector<string>& board, int x0, int y0, int x1, int y1) {
  int n = board.size();
  int m = board[0].size();
  vector<vector<bool>> flag(n, vector<bool>(m, false));

  //因此初始局面是合法的，因此第一次只需要考虑交换的两个位置；
  markBoards(board, flag, x0, y0);
  markBoards(board, flag, x1, y1);

  int count = INT_MAX;
  int result = 0;

  //没有可消除的跳出循环
  while (count > 0) {    
    //遍历整个局面，计算消除个数，并消除方块，垂直下降，返回消除个数
    count = EliminateAndCount(board, flag);
    result += count;

    //对下降后的新的局面重新标记
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (board[i][j] != '.') {
          markBoards(board, flag, i, j);
        }
      }
    }
  }
  return result;
}

int main()
{
  int s, n, m;
  cin >> s;
  while (s--) {
    cin >> n >> m;
    vector<string> board(n);
    for (int i = 0; i < n; ++i) {
      cin >> board[i];
    }
    int x0, y0, x1, y1;
    cin >> x0 >> y0 >> x1 >> y1;

    //检查输入输出是否越界
    if (x0 < 0 || x0 >= n || y0 < 0 || y0 >= m 
      || x1 < 0 || x1 >= n || y1 < 0 || y1 >= m 
      || (x0 != x1 && y0 != y1)
      || (x0 == x1 && y0 == y1)) {
        cout << "0" << endl;
        continue;
    }

    //交换两个点
    char c = board[x0][y0];
    board[x0][y0] = board[x1][y1];
    board[x1][y1] = c;

    int result = 0; 
    result = iterEliminateGame(board, x0, y0, x1, y1);
    cout << result << endl;
  }
  return 0;
}





转载请标明文章出处。本文内容为实践后的原创整理，如果侵犯了您的版权，请联系我进行删除，邮件：yanhealth@163.com

文章目录