Йохохо, %USERNAME%! Прошло уже много времени с момента последней записки. Сдается мне, ты жаждешь новых знаний? И я тоже ;) Итак. Сегодяншний разбор посвящен заданию №4 «Маджонг». Подробности под катом!
Все разборы:
- Разбор задач с “Ломоносова” по информатике, ч. 1
- Разбор задач с “Ломоносова” по информатике, ч. 2
- Разбор задач с “Ломоносова” по информатике, ч.3
Не стану скрывать факт того, что я- закоренелый веб- девелопер. Моя стезя PHP, Python, JS. Ну, чутка C++. А что из этого следует? Правильно: ничего. Как не печально, но это задание я не решил. А почему эта записка существует? Сорцы я использую нагло и без разрешения, и разбираться будем вместе.
Если тебе не интересен полный исходный код, прошу в конец записки за листингом на Processing( потомок Java), иначе: «Да начнется экшн!» :) Скачать все задачи можно тут.
Дисклеймер: я не знаком с Java, потому прошу не ругать за ошибки в описаниях..
Условие задачи
В решении задачи обязательно указывайте использованные источники информации о
правилах игры (например, ссылки на веб сайты). Рассмотрим упрощенный вариант игры Маджонг,
в которой 32 пары костей, занумерованных числами от 1 до 32, выкладываются на игровом поле в
куб размером 4x4x4. Куб состоит из 4 слоев (первый слой – самый нижний, а четвертый – самый
верхний). Каждый слой состоит из 16 костей, выложенных в квадрат 4×4. Кости слоев лежат
строго друг на друге.
Конфигурацию игрового поля назовем тупиковой, если в этой конфигурации нельзя снять ни
одной пары костей. Дана начальная конфигурация игрового поля. Определите сумму номеров
костей, оставшихся на игровом поле в тупиковой конфигурации… *4 таблички с конфигами*.
Итак. Для начала нам нужны правила игры в Маджонг хотя бы потому, что их врядли кто- то знает. Гуглим и на вики находим в правилах следующее:
- Снимать можно только две одинаковые кости за раз. В условии сказано, что кости обозначены цифрами
- Снимать можно только незакрытые сверху кости. По условию они расположены
не в виде пирамиды, а кубом, следовательно кость может быть блокирована только одной костью сверху - У кости должна быть как минимум пара свободных соседних костей на том же уровне, иначе её
нельзя снять
Теперь по кусочкам разберем код в конце записки:
Класс «Rect». Если я правильно понял, то этот класс отвечает за создание куба и проверку его на существование.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Rect { int x1, x2; int y1, y2; int h1, h2; Rect(int x, int y, int hx, int hy) { x1 = x; x2 = x1 + hx; y1 = y; y2 = y1 + hy; h1 = hx; h2 = hy; } boolean isIn(int x, int y) { if (x <= x2 && x >= x1) if (y <= y2 && y >= y1) return true; return false; } } |
Класс «Bone».
- Метод Rect rect() возвращает кость по заданным координатам
- Метод bone создает кость в заданных координатах
- res() обнуляет элемент трехмерного массива по координатам x,y,h
- До сокрального смысла eq() я так и не додумал :)
- И конечно же метод Free, который освобождает кость по координатам
|
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 |
class Bone { int x, y, h; Bone(int xx, int yy, int hh) { x = xx; y = yy; h = hh; } Rect rect() { return rectFor(x, y, h); } int bone() { return board[h][x][y]; } void res() { board[h][x][y] = 0; } boolean eq(int xx, int yy, int hh) { return (x == xx) && (y == yy) && (h == hh); } boolean free() { return getValue(x + 1, y, h) + getValue(x - 1, y, h) <=1; } } |
Функции и переменные
Первым делом автор программы задает конфигурацию поля из условия задачи в трехмерном массиве:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
int board[][][] = { { {30, 17, 10, 17}, {25, 13, 15, 8}, {27, 13, 3, 8}, {2, 12, 31, 12} }, { {19, 24, 26, 6}, {1, 15, 23, 24}, {3, 14, 28, 6}, {16, 28, 5, 29} }, { {11, 23, 14, 32}, {4, 16, 20, 7}, {31, 32, 11, 2}, {18, 27, 7, 1} }, { {29, 26, 5, 25}, {21, 21, 9, 20}, {10, 19, 4, 30}, {22, 22, 9, 18} } }; |
Дальше определяет размеры куба относительно всего размера рабочей области и переменную hmw:
|
1 2 3 4 5 6 7 8 |
int size1 = 100; int size2 = 50; int boardx = (640 - size1 * 4)/2; int boardy = (480 - size1 * 4)/2; int hmv = 4; Bone c1, c2; Bone hd; |
Processing ведь очень хорошо подходит для прототипирования графических приложений, а потому создается рабочая область 640х480
|
1 2 3 4 |
void setup() { size(640, 480); textAlign(CENTER, CENTER); } |
И функция, рисующая кости:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void draw() { background(#A2A2A2); int summ = 0; for (int lh = 0; lh <= 3; lh++) for (int lx = 0; lx <= 3; lx++) for (int ly = 0; ly <= 3; ly++) { drawBone(lx, ly, lh, board[lh][lx][ly]); summ += board[lh][lx][ly]; } text(summ, 30, 30); } |
В классе Rect определяется метод rectFor()
|
1 2 3 4 |
Rect rectFor(int x, int y, int h) { return new Rect(boardx + x * size1 + h * hmv, boardy + y * size1 + h * hmv, size2, size2); } |
Функция isUpperOn возвращает true, если над костью нет другой и false, если есть:
|
1 2 3 4 5 6 7 8 9 |
boolean isUpperOn(int x, int y, int h) { for (int lh = 3; lh >= 0; lh--) { if (h == lh) return true; else if (board[lh][x][y] != 0) return false; } return false; } |
Функция getValue, как очевидно из названия, извлекает из трехмерного массива значение кости по координатам
|
1 2 3 4 5 6 7 |
int getValue(int x, int y, int h) { if (x < 0 || x > 3 || y < 0 || y > 3) return 0; if (board[h][x][y] != 0) return 1; return 0; } |
А теперь то, без чего совершенно точно ничего реботать не будет. pushBone() убирает кость, получая на входе ее объект класса Bone
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void pushBone(Bone b) { if (c1 != null && c1 == b) return; c2 = c1; c1 = b; if (c1 != null && c2 != null) if (c1.bone() == c2.bone() && c1.free() && c2.free()) { c1.res(); c2.res(); c1 = null; c2 = null; } } |
Так как тулза графическая, то необходимо обрабатывать нажатия мыши
|
1 2 3 4 |
void mouseClicked() { if (hd != null && hd.rect().isIn(mouseX, mouseY)) pushBone(hd); } |
Не совсем понял, что делает функция checkForChecked, буду рад, если кто- то подскажет
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
boolean checkForChecked(int x, int y, int h) { if (c1 != null) { if (c1.eq(x, y, h) && c1.free()) { return true; } } if (c2 != null) { if (c2.eq(x, y, h) && c2.free()) { return true; } } return false; } |
И наконец то, что будет это все связывать воедино и рендерить: функция drawBone
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void drawBone(int x, int y, int h, int bone) { if (bone == 0) return; Rect r = rectFor(x, y, h); Bone t = new Bone(x, y, h); if (checkForChecked(x, y, h)) fill(#FFCCAA); else if (r.isIn(mouseX, mouseY) && isUpperOn(x, y, h) && t.free()) { fill(#AACCFF); hd = t; } else fill(color(50 + (bone % 10) * 30, 100 + (bone / 10) * 10, 255)); pushMatrix(); translate(r.x1, r.y1); rect(0, 0, r.h1, r.h2); fill(0); text(bone, size2/2, size2/2); popMatrix(); } |
После компиляции и запуска программы мы убеждаемся, что помимо нескольких костей ничего не снять, а сумма оставшихся равна 1056.
Итак, ответ задачи: 1056.
Записка, я так думаю, получилась отвратительная. Но я надеюсь, что маньяк, знающий Java, поможет мне понять и поподробнее описать все это.
Спасибо за прочтение, %USERNAME%, удачного кодинга, интересных реальных задач и адекватных клиентов!
Листинг решения задачи №4 «Маджонг» на Processing
|
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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 |
class Rect { int x1, x2; int y1, y2; int h1, h2; Rect(int x, int y, int hx, int hy) { x1 = x; x2 = x1 + hx; y1 = y; y2 = y1 + hy; h1 = hx; h2 = hy; } boolean isIn(int x, int y) { if (x <= x2 && x >= x1) if (y <= y2 && y >= y1) return true; return false; } } class Bone { int x, y, h; Bone(int xx, int yy, int hh) { x = xx; y = yy; h = hh; } Rect rect() { return rectFor(x, y, h); } int bone() { return board[h][x][y]; } void res() { board[h][x][y] = 0; } boolean eq(int xx, int yy, int hh) { return (x == xx) && (y == yy) && (h == hh); } boolean free() { return getValue(x + 1, y, h) + getValue(x - 1, y, h) <=1; } } int board[][][] = { { {30, 17, 10, 17}, {25, 13, 15, 8}, {27, 13, 3, 8}, {2, 12, 31, 12} }, { {19, 24, 26, 6}, {1, 15, 23, 24}, {3, 14, 28, 6}, {16, 28, 5, 29} }, { {11, 23, 14, 32}, {4, 16, 20, 7}, {31, 32, 11, 2}, {18, 27, 7, 1} }, { {29, 26, 5, 25}, {21, 21, 9, 20}, {10, 19, 4, 30}, {22, 22, 9, 18} } }; int size1 = 100; int size2 = 50; int boardx = (640 - size1 * 4)/2; int boardy = (480 - size1 * 4)/2; int hmv = 4; Bone c1, c2; Bone hd; void setup() { size(640, 480); textAlign(CENTER, CENTER); } void draw() { background(#A2A2A2); int summ = 0; for (int lh = 0; lh <= 3; lh++) for (int lx = 0; lx <= 3; lx++) for (int ly = 0; ly <= 3; ly++) { drawBone(lx, ly, lh, board[lh][lx][ly]); summ += board[lh][lx][ly]; } text(summ, 30, 30); } Rect rectFor(int x, int y, int h) { return new Rect(boardx + x * size1 + h * hmv, boardy + y * size1 + h * hmv, size2, size2); } boolean isUpperOn(int x, int y, int h) { for (int lh = 3; lh >= 0; lh--) { if (h == lh) return true; else if (board[lh][x][y] != 0) return false; } return false; } int getValue(int x, int y, int h) { if (x < 0 || x > 3 || y < 0 || y > 3) return 0; if (board[h][x][y] != 0) return 1; return 0; } void pushBone(Bone b) { if (c1 != null && c1 == b) return; c2 = c1; c1 = b; if (c1 != null && c2 != null) if (c1.bone() == c2.bone() && c1.free() && c2.free()) { c1.res(); c2.res(); c1 = null; c2 = null; } } void mouseClicked() { if (hd != null && hd.rect().isIn(mouseX, mouseY)) pushBone(hd); } boolean checkForChecked(int x, int y, int h) { if (c1 != null) { if (c1.eq(x, y, h) && c1.free()) { return true; } } if (c2 != null) { if (c2.eq(x, y, h) && c2.free()) { return true; } } return false; } void drawBone(int x, int y, int h, int bone) { if (bone == 0) return; Rect r = rectFor(x, y, h); Bone t = new Bone(x, y, h); if (checkForChecked(x, y, h)) fill(#FFCCAA); else if (r.isIn(mouseX, mouseY) && isUpperOn(x, y, h) && t.free()) { fill(#AACCFF); hd = t; } else fill(color(50 + (bone % 10) * 30, 100 + (bone / 10) * 10, 255)); pushMatrix(); translate(r.x1, r.y1); rect(0, 0, r.h1, r.h2); fill(0); text(bone, size2/2, size2/2); popMatrix(); } |
