本文共 4678 字，大约阅读时间需要 15 分钟。
#include#include #include #include using namespace std;const int MAX = 400;char str[MAX][MAX];int n, m;bool vis[MAX][MAX];int eight[8][2] = {-1,-1, -1,0, -1,1, 0,-1, 0,1, 1,-1, 1,0, 1,1};int dfs(int x, int y) { int ans = 1, tx, ty; for (int i = 0; i < 8; ++i) { tx = x + eight[i][0]; ty = y + eight[i][1]; if (tx < 0 || ty < 0 || tx >= n || ty >= m || vis[tx][ty]) continue; if (str[tx][ty] == 'M') { vis[tx][ty] = true; ans += dfs(tx, ty); } } return ans;}char get(int x, int y) { int sum = dfs(x, y); if (sum == 22) return 'I'; else if (sum == 24) return 'L'; else if (sum == 27) return 'J'; else if (sum == 28) return 'Y'; else if (sum == 31) return 'Z'; else if (sum == 33) return 'A'; else if (sum == 37) return 'H'; else if (sum == 44) return 'E'; else if (sum == 48) return 'Q'; else if (sum == 49) return 'B'; else if (sum == 34) { int tmp = 0; for (int i = y; str[x][i] == 'M'; ++i, ++tmp); if (tmp == 8) return 'C'; else return 'T'; } else if (sum == 36) { int tmp = 0; for (int i = y; str[x][i] == 'M'; ++i, ++tmp); if (tmp == 4) return 'K'; else if (tmp > 4) return 'F'; else if (str[x+3][y+2] == 'M') return 'K'; else return 'F'; } else if (sum == 38) { int up = 0; for (int i = y; str[x][i] == 'M'; ++i, ++up); if (up == 8 || up == 9) return 'G'; else if (up == 11) return 'P'; else if (up == 10) return 'U'; else if (str[x+6][y] == 'M') return 'P'; else return 'U'; } else if (sum == 40) { int tmp = 0; for (int i = y; str[x][i] == 'M'; ++i, ++tmp); if (tmp == 6) return 'O'; else if (tmp == 4 || tmp == 0) return 'V'; else if (tmp == 2) return 'W'; else if (str[x+1][y] == 'M') return 'W'; else return 'X'; } else if (sum == 42) { int tmp = 0; for (int i = y; str[x][i] == 'M'; ++i, ++tmp); if (tmp == 11) return 'D'; else if (tmp == 2) return 'M'; else return 'N'; } else if (sum == 43) { int tmp = 0; for (int i = y; str[x][i] == 'M'; ++i, ++tmp); if (tmp == 7 || tmp == 8) return 'S'; return 'R'; }}int main() { while (~scanf(" %d %d", &n, &m)) { memset(str, '\0', sizeof(str)); for (int i = 0; i < n; ++i) scanf(" %s", str[i]); memset(vis, false, sizeof(vis)); set ans; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!vis[i][j] && str[i][j] == 'M') { vis[i][j] = true; ans.insert(get(i,j)); } } } for (set ::iterator it = ans.begin(); it != ans.end(); ++it) putchar(*it); putchar('\n'); } return 0;}#include #include char str[400][400];int go[8][2] = { {-1,-1},{-1,0},{-1,1},{ 0,-1},{ 0,1},{ 1,-1},{ 1,0},{ 1,1}};int quex[1000];int quey[1000];int hd, tl;int n, m;int hashval[] = {1820037518 ,1427144302 ,199583009 ,1249776443 ,453658630 ,65003669 ,1043308300 ,882353686 ,1672668286 ,1509684428 ,1548535098 ,1056054947 ,1302071887 ,2000359048 ,546491766 ,48868777 ,855939341 ,241813173 ,1412862443 ,1596380393 ,873602306 ,96302682 ,601941967 ,331153068 ,557269562 ,1950483894};int fanval[] = {782407826 ,1124626577 ,331153068 ,1840406677 ,613954835 ,2117754741 ,2069844786 ,2107056447 ,1995789168 ,820763120 ,1348692044 ,546491766 ,1233523538 ,1982946365 ,751655839 ,1274392924 ,2059859316 ,1672668286 ,882353686 ,512227380 ,1553622659 ,843347556 ,80940987 ,1629310428 ,102062630 ,2037627779};int hash(int si, int sj) { hd = tl = 0; quex[tl] = si; quey[tl] = sj; tl++; str[si][sj] = '0'; unsigned long long hashnum = 0; int seed = 13131; while (hd < tl) { int nowx = quex[hd]; int nowy = quey[hd]; hd++; for (int i = 0; i < 8; i++) { int nx = nowx + go[i][0]; int ny = nowy + go[i][1]; if (0 <= nx && nx < n && 0 <= ny && ny <= m) { if (str[nx][ny] == 'M') { str[nx][ny] = '0'; hashnum = hashnum*seed+i; quex[tl] = nx; quey[tl] = ny; tl++; } } } } return hashnum & (-1u/2);}bool vis[500];int main() { while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i < n; i++) { scanf("%s",str[i]); } memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (str[i][j] == 'M') { int val = hash(i,j); //printf("%d\n", val); for (int k = 0; k < 26; k++) { if (val == hashval[k] || val == fanval[25-k]) { vis[k+'A'] = true; //printf("%c\n", k+'a'); break; } } } } } for (char i = 'A'; i <= 'Z'; i++) { if (vis[i]) { printf("%c", i); } }puts(""); } return 0;}
转载地址：http://mcbci.baihongyu.com/