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
|
import string import copy dir_array = [160, 142, 226, 128, 189, 158, 130, 145, 29, 181, 223, 138, 200, 152, 4, 76, 25, 83, 197, 181, 50, 204, 116, 198, 72, 96, 183, 251, 41, 63, 46, 254, 237, 155, 86, 206, 116, 155, 94, 132, 228, 54, 226, 88, 104, 140, 83, 246, 81, 19, 145, 255, 1, 140, 65, 82, 71, 102, 206, 34, 69, 75, 228, 220, 104, 128, 91, 76, 206, 194, 115, 158, 123, 2, 4, 114, 85, 189, 0, 149, 132, 45, 219, 153, 154, 31, 179, 30, 108, 199, 224, 34, 223, 110, 235, 106, 181, 124, 175, 250, 214, 172, 45, 74, 147, 120, 191, 60, 26, 210, 224, 47, 221, 70, 99, 142, 20, 78, 84, 83, 237, 163, 210, 66, 34, 140, 192, 251, 98, 166, 145, 195, 245, 35, 254, 190, 229, 70, 14, 21, 245, 32, 14, 145, 27, 151, 6, 43, 154, 205, 10, 91, 151, 60, 229, 182, 26, 188, 125, 81, 160, 163, 207, 130, 19, 22, 144, 144, 124, 173, 222, 182, 135, 239, 83, 56, 250, 207, 186, 211, 238, 53, 103, 198, 56, 67, 145, 218, 190, 192, 235, 210, 103, 131, 231, 18, 156, 113, 172, 180, 93, 155, 219, 96, 41, 176, 29, 167, 33, 158, 1, 13, 137, 166, 13, 148, 195, 115, 121, 129, 189, 232, 133, 94, 41, 78, 195, 120, 91, 187, 114, 187, 153, 30, 51, 223, 142, 239, 127, 105, 200, 47, 149, 88, 65, 223, 1, 4, 46, 203, 181, 6, 38, 237, 131, 167, 107, 60, 241, 161, 110, 221, 175, 181, 236, 90, 226, 96, 22, 113, 30, 135, 136, 212, 26, 111, 131, 31, 187, 131, 106, 71, 91, 235, 254, 43, 8, 52, 166, 83, 62, 151, 36, 29, 250, 97, 202, 131, 236, 159, 172, 40, 21, 61, 192, 62, 173, 26, 191, 168, 121, 115, 227, 37, 198, 87, 235, 204, 51, 45, 220, 155, 84, 104, 50, 37, 212, 59, 175, 177, 104, 156, 119, 110, 195, 202, 217, 188, 160, 122, 51, 180, 239, 20, 133, 232, 58, 235, 166, 68, 38, 209, 4, 187, 209, 41, 133, 28, 230, 60, 234, 69, 194, 213, 214, 14, 206, 241, 60, 239, 167, 126, 216, 175, 184, 138, 229, 125, 254, 30, 50, 122, 24, 4, 150, 33, 139, 127, 65, 58, 104, 102, 80, 76, 37, 29, 25, 65, 14, 61, 58, 101, 30, 94, 205, 242, 78, 63, 124, 163, 60, 45, 85, 0, 18, 78, 74, 215, 49, 147, 80, 138, 185, 30, 43, 169, 157, 223, 169, 77, 131, 97, 151, 75, 147, 251, 99, 23, 251, 32, 19, 122, 166, 209, 129, 120, 90, 204, 165, 28, 51, 79, 104, 19, 31, 75, 111, 167, 37, 201, 35, 248, 120, 215, 234, 80, 82, 255, 2, 92, 64, 105, 3, 93, 22, 39, 1, 139, 231, 71, 46, 214, 24, 67, 22, 230, 3, 213, 188, 20, 110, 180, 122, 237, 48, 132, 184, 238, 205, 40, 177, 198, 29, 201, 88, 100, 102, 253, 178, 56, 201, 223, 156, 105, 251, 137, 234, 121, 171, 236, 154, 232, 228, 203, 35, 131, 230, 83, 185, 250, 68, 200, 192, 93, 101, 223, 191, 77, 130, 122, 205, 18, 100, 135, 199, 68, 22, 236, 63, 81, 2, 154, 210, 222, 127, 18, 113, 32, 114, 18, 114, 205, 1, 140, 82, 178, 180, 226, 71, 165, 91, 57, 246, 111, 169, 97, 45, 194, 116, 127, 232, 124, 11, 69, 71, 17, 26, 4, 50, 241, 18, 39, 116, 81, 70, 72, 109, 26, 134, 206, 15, 241, 49, 64, 97, 16, 133, 176, 96, 247, 184, 228, 238, 189, 177, 80, 103, 73, 2, 102, 232, 152, 93, 2, 15, 190, 127, 157, 39, 138, 91, 13, 150, 252, 49, 193, 212, 145, 209, 180, 21, 88, 140, 233, 8, 113, 236, 2, 118, 141, 204, 110, 209, 36, 229, 212, 149, 76, 110, 57, 166, 196, 22, 16, 207, 98, 77, 40, 156, 117, 192, 120, 203, 174, 49, 251, 25, 197, 140, 9, 156, 203, 37, 21, 76, 100, 184, 201, 240, 36, 214, 236, 38, 183, 167, 27, 125, 150, 245, 186, 248, 163, 192, 236, 107, 237, 104, 31, 0, 46, 231, 137, 38, 161, 73, 44, 235, 239, 187, 145, 212, 110, 84, 37, 159, 51, 155, 137, 197, 175, 118, 225, 142, 77, 36, 71, 198, 132, 27, 209, 207, 168, 57, 70, 11, 120, 22, 115, 96, 201, 160, 229, 95, 248, 182, 43, 24, 60, 102, 119, 13, 159, 30, 111, 254, 195, 65, 97, 111, 161, 140, 45, 160, 87, 106, 195, 50, 131, 54, 126, 60, 232, 29, 54, 76, 68, 99, 45, 107, 56, 238, 187, 148, 246, 83, 42, 69, 225, 248, 162, 17, 116, 117, 47, 249, 148, 150, 32, 158, 137, 110, 3, 218, 80, 13, 121, 22, 227, 113, 241, 154, 238, 191, 10, 247, 126, 59, 232, 251, 162, 49, 151, 109, 18, 204, 1, 101, 173, 129, 112, 236, 75, 73, 214, 98, 211, 216, 228, 4, 100, 67, 114, 143, 62, 212, 214, 124, 167, 189, 136, 161, 228, 56, 77, 165, 76, 222, 111, 138, 184, 163, 98, 113, 103, 19, 74, 59, 233, 199, 242, 151, 129, 51, 15, 60, 102, 237, 134, 205, 1, 14, 212, 57, 13, 167, 193, 171, 80, 133, 193, 46, 186, 251, 157, 222, 169, 201, 160, 44, 185, 123, 129, 215, 72, 251, 250, 211, 242, 92, 83, 142, 98, 116, 189, 184, 95, 167, 138, 238, 125, 169, 137, 124, 60, 33, 234, 161, 206, 143, 15, 31, 180, 54, 185, 130, 77, 252, 237, 37, 180, 218, 240, 17, 43, 189, 184, 238, 234, 154, 166, 68, 204, 164, 209, 72, 212, 17, 24, 123, 46, 117, 132, 87, 125, 27, 204, 190, 12, 187, 85, 202, 159, 86, 41, 205, 52, 238, 208, 88, 122, 46, 139, 252, 72, 163, 162, 156, 125, 91, 154] dir_arr = [0, 1, 0, -1, 1, 0, -1, 0] def make_target(): target = [] for i in xrange(10): target.append([]) for j in xrange(10): target[i].append(i*10 + j) return target def do_traceback(x, y): target = make_target() for i in xrange(1000): v7 = dir_array[i] for j in xrange(4): v8 = (v7 >> ((3 - j) * 2)) & 3 v9 = 5 - v8 if v8 < 2: v9 = 1 - v8 last_x = x - dir_arr[v9 * 2] last_y = y - dir_arr[v9 * 2 + 1] if last_x < 0 or last_x >= 10 or last_y < 0 or last_y >= 10: return None tmp = target[last_x][last_y] target[last_x][last_y] = target[x][y] target[x][y] = tmp x = last_x y = last_y if target[x][y] != 0: print 'No' return None return target def find_start(target): for i in xrange(10): for j in xrange(10): if target[i][j] == 0: return i, j raise Exception("No zero in matrix"); def do_run(target, x, y): for i in range(1000)[::-1]: v7 = dir_array[i] for j in xrange(4): v8 = v7 & 3 v7 = v7 >> 2 v9 = 5 - v8 if v8 < 2: v9 = 1 - v8 next_x = x + dir_arr[v9*2] next_y = y + dir_arr[v9*2+1] if next_x >= 10 or next_x < 0 or next_y >= 10 or next_y < 0: return False tmp = target[next_x][next_y] target[next_x][next_y] = target[x][y] target[x][y] = tmp x = next_x y = next_y for i in xrange(10): for j in xrange(10): if target[i][j] != i * 10 + j: return False return True for k in xrange(10): for l in xrange(10): result = do_traceback(k, l) if result: print result backup = copy.deepcopy(result) x, y = find_start(result) if do_run(result, x, y) == True: encoded = '' for i in xrange(10): for j in xrange(10): hi = backup[i][j] / 0x10 lo = backup[i][j] % 0x10 encoded += string.ascii_uppercase[hi] encoded += string.ascii_uppercase[lo] print encoded
|