Uva 1103 Ancient Messages

大致思路是DFS：

　　1. 每个图案所包含的白色连通块数量不一：

　　　　　　Ankh : 1 ;  Wedjat : 3  ; Djed : 5   ;   Scarab : 4 ; Was : 0  ;  Akeht : 2

　　根据每个图包含的白色连通块判断是哪个图案

　　2. 两个Dfs函数，一个判断白色，一个判断黑色；判断黑色的Dfs，一旦发现白色，就调用判断白色的Dfs，同时白色连通块计数器加一

　　3. 我开始比较疑惑的一个地方是：如何判断这个白色块是在一个黑色图案里面还是外面？后来才明白：只要一开始在图外面再加一层白色框框，然后开始访问白色，把此时访问到的所有白色设为不可访问即可，这样子就不会把图案里面的白色连通块和外面的混淆了

 

一点感悟和收获：这题确实再某种程度上刷新了我“的世界观“，初看题意，啥想法都没有，后来再看看书，再看看别人的题解，才发现，这题实在太简单了！说白了，一开始把题目想复杂了，没发现浅显的规律，如果能静下心来，仔细发现规律的话，这题真的比我最初想像的简单太多了！

 

参考资料：

　　1. http://www.cnblogs.com/hanbinggan/p/4225044.html

　　2. 《算法竞赛入门经典（第二版）》

 

#include <bits/stdc++.h>using namespace std;const int MAXN = 200 + 10; int plan[MAXN][MAXN]; int counter[MAXN]; char apl[] = "ADJKSW"; int H, W;void Read() {memset(plan, 0, sizeof(plan));char c;int pos;for(int i=1; i<=H; i++) {pos = 1;for(int j=1; j<=W; j++) {cin >> c;if(isalpha(c)) {c = c - 'a' + 10;} else {c = c - '0';}// Transfer to binarypos += 3;for(int k=0; k<4; k++) {plan[i][pos --] = c % 2;c /= 2;}pos +=5;}}W *= 4; }bool Inside(int x, int y) {return x>=0 && x<=H+1 && y>=0 && y<=W+1; }int cnt; void DfsWhite(int x, int y) {if(!Inside(x, y) || plan[x][y]!=0) {return ;}plan[x][y] = -1;DfsWhite(x, y+1);DfsWhite(x, y-1);DfsWhite(x+1, y);DfsWhite(x-1, y); }void DfsBlack(int x, int y) {if(!Inside(x, y) || plan[x][y] == -1) return ;if(plan[x][y] == 0) {++ cnt;DfsWhite(x, y);return ;}plan[x][y] = -1;DfsBlack(x, y+1);DfsBlack(x, y-1);DfsBlack(x+1, y);DfsBlack(x-1, y); }int Case = 0; void Work() {Read();DfsWhite(0, 0); // the white blocks outside the hieroglyphsmemset(counter, 0, sizeof(counter));for(int i=1; i<=H; i++) {for(int j=1; j<=W; j++) {if(plan[i][j] == 1) {cnt = 0;DfsBlack(i, j);switch(cnt) {case 0: counter['W'] ++; break;case 1: counter['A'] ++; break;case 2: counter['K'] ++; break;case 3: counter['J'] ++; break;case 4: counter['S'] ++; break;case 5: counter['D'] ++; break;}}}}cout << "Case " << (++Case) << ": ";for(int i=0; i<6; i++) {for(int j=0; j<counter[apl[i]]; ++j) {cout << apl[i];}}cout << endl; }int main() {ios::sync_with_stdio(false);cin.tie(0);while(cin >> H >> W && (H + W)) {Work();}return 0; }

 

转载于:https://www.cnblogs.com/Emerald/p/4723653.html

总结

以上是生活随笔为你收集整理的Uva 1103 Ancient Messages的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。