首页 > 代码库 > UVA1003(dfs+进制转换)
UVA1003(dfs+进制转换)
题意:输入很多字符的16进制数,现在需要你先转化为2进制,之后二进制中1和0组成的字符需要你求出来。
思路:字符每一个都有所不同可以靠圆圈的数目求出。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int gragh[1000][1000]; int n,m; int ans; int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; void change(char c,int x,int y) { if(c >= ‘0‘ && c <= ‘9‘){ int d = c - ‘0‘; gragh[x][(y-1)*4+4] = d%2;d /= 2; gragh[x][(y-1)*4+3] = d%2;d /= 2; gragh[x][(y-1)*4+2] = d%2;d /= 2; gragh[x][(y-1)*4+1] = d%2; } else { int d = c - ‘a‘ + 10; gragh[x][(y-1)*4+4] = d%2;d /= 2; gragh[x][(y-1)*4+3] = d%2;d /= 2; gragh[x][(y-1)*4+2] = d%2;d /= 2; gragh[x][(y-1)*4+1] = d%2; } } void dfs1(int x,int y) //作用是把1.没用的0清掉 2.没遇到一种情况就把0清掉 { gragh[x][y] = -1; for(int i = 0;i < 4; i++){ int xx = x + dir[i][0]; int yy = y + dir[i][1]; if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && gragh[xx][yy] == 0){ dfs1(xx,yy); } } } void dfs2(int x,int y) { gragh[x][y] = -1; for(int i = 0;i < 4; i++){ int xx = x + dir[i][0]; int yy = y + dir[i][1]; if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && gragh[xx][yy] == 0){ ans++; //记录每一种字符的圈数 dfs1(xx,yy); } else if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && gragh[xx][yy] == 1){ dfs2(xx,yy); } } } int main() { // freopen("in.txt","r",stdin); int ncase = 1; while(scanf("%d%d",&n,&m) != EOF){ if(n == 0 && m == 0) break; memset(gragh,0,sizeof(gragh)); char a[100]; for(int i = 1;i <= n; i++){ scanf("%s",a+1); for(int j = m;j >= 1; j--){ change(a[j],i,j); //分别是十六进制的数,第几行,第几列 } } m *= 4; for(int i = 1;i <= n; i++){ if(gragh[i][1] == 0){ dfs1(i,1); } if(gragh[i][m] == 0){ dfs1(i,m); } } for(int j = 1;j <= m; j++){ if(gragh[1][j] == 0){ dfs1(1,j); } if(gragh[n][j] == 0){ dfs1(n,j); } } int pos = 0; char s[100]; for(int i = 1;i <= n; i++){ for(int j = 1;j <= m; j++){ ans = 0; if(gragh[i][j] == 1){ dfs2(i,j); if(ans == 1) s[pos++] = ‘A‘; else if(ans == 3) s[pos++] = ‘J‘; else if(ans == 5) s[pos++] = ‘D‘; else if(ans == 4) s[pos++] = ‘S‘; else if(ans == 0) s[pos++] = ‘W‘; else if(ans == 2) s[pos++] = ‘K‘; } } } sort(s,s+pos); printf("Case %d: ",ncase++); for(int i = 0;i < pos; i++) printf("%c",s[i]); printf("\n"); } return 0; }
UVA1003(dfs+进制转换)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。