题目大意：一矩形区域中有若干个箱子，每次能从上下左右四个方向推箱子，被推的箱子往前移动，但是不能被挤爆。
解题思路：直接模拟。
代码如下：
1 #include <cstdio> 2 #include <iostream> 3 #include <string> 4 #include <algorithm> 5 using namespace std; 6 const int maxd = 25; 7 8 bool matrix[maxd][maxd]; // matrix[i][j] == true 表示位置(i,j)有内容 9 int vertical[maxd]; 10 int horizonal[maxd]; 11 12 13 void init(const int &rows, const int &cols) { 14 for (int r = 0; r <= rows; ++r) 15 for (int c = 0; c <= cols; ++c) 16 matrix[r][c] = false; 17 } 18 19 void fillRight(const int &r, const int &c) { 20 if (matrix[r][c]) { 21 fillRight(r, c + 1); 22 } else { 23 matrix[r][c] = true; 24 } 25 } 26 27 void fillLeft(const int &r, const int &c) { 28 if (matrix[r][c]) { 29 fillLeft(r, c - 1); 30 } else { 31 matrix[r][c] = true; 32 } 33 } 34 35 void fillDown(const int &r, const int &c) { 36 if (matrix[r][c]) { 37 fillDown(r + 1, c); 38 } else { 39 matrix[r][c] = true; 40 } 41 } 42 43 void fillUp(const int &r, const int &c) { 44 if (matrix[r][c]) { 45 fillUp(r - 1, c); 46 } else { 47 matrix[r][c] = true; 48 } 49 } 50 51 int main() { 52 int t = 0; 53 int rows, cols; 54 string right("right"); 55 string left("left"); 56 string down("down"); 57 string up("up"); 58 string done("done"); 59 60 while (++t, scanf("%d%d", &rows, &cols), rows && cols) { 61 init(rows, cols); 62 int n; 63 scanf("%d", &n); 64 int row, col; 65 for (int i = 0; i < n; ++i) { 66 scanf("%d%d", &row, &col); 67 matrix[row][col] = true; 68 } 69 70 string op; 71 int opNum; 72 while (cin >> op, op != done) { 73 cin >> opNum; 74 for (int i = 0; i < rows; ++i) horizonal[i] = 0; 75 for (int i = 0; i < cols; ++i) vertical[i] = 0; 76 for (int r = 0; r < rows; ++r) { 77 for (int c = 0; c < cols; ++c) { 78 if (matrix[r][c]) { 79 ++horizonal[r]; 80 ++vertical[c]; 81 } 82 } 83 } 84 int maxHorizonal = 0, maxVertical = 0; 85 for (int i = 0; i < rows; ++i) maxHorizonal = max(maxHorizonal, horizonal[i]); 86 for (int i = 0; i < cols; ++i) maxVertical = max(maxVertical, vertical[i]); 87 88 if (op == left) { 89 int bound = min(opNum, cols - maxHorizonal); 90 int begin = cols - 1, end = begin - bound; 91 int count = 0; 92 for (int r = 0; r < rows; ++r) { 93 for (int c = begin; c > end; --c) { 94 if (matrix[r][c]) { 95 matrix[r][c] = false; 96 fillLeft(r, end - count); 97 } 98 } 99 } 100 } else if (op == right) { 101 int bound = min(opNum, cols - maxHorizonal); 102 int begin = 0, end = bound; // 左闭右开 103 int count = 0; 104 for (int r = 0; r < rows; ++r) { 105 for (int c = begin; c < end; ++c) { 106 if (matrix[r][c]) { 107 matrix[r][c] = false; // 撤销位置中的物质 108 fillRight(r, end + count); 109 } 110 } 111 } 112 } else if (op == up) { 113 int bound = min(opNum, rows - maxVertical); 114 int begin = rows - 1, end = begin - bound; 115 int count = 0; 116 for (int c = 0; c < cols; ++c) { 117 for (int r = begin; r > end; --r) { 118 if (matrix[r][c]) { 119 matrix[r][c] = false; 120 fillUp(end - count, c); 121 } 122 } 123 } 124 } else if (op == down) { 125 int bound = min(opNum, rows - maxVertical); 126 int begin = 0, end = bound; 127 int count = 0; 128 for (int c = 0; c < cols; ++c) { 129 for (int r = begin; r < end; ++r) { 130 if (matrix[r][c]) { 131 matrix[r][c] = false; 132 fillDown(end + count, c); 133 } 134 } 135 } 136 } 137 138 } 139 // 输出 140 printf("Data set %d ends with boxes at locations", t); 141 for (int r = 0; r < rows; ++r) { 142 for (int c = 0; c < cols; ++c) { 143 if (matrix[r][c]) { 144 printf(" (%d,%d)", r, c); 145 } 146 } 147 } 148 printf(". "); 149 } 150 return 0; 151 }