当前位置: 代码迷 >> 综合 >> uva1103 Ancient Messages(dfs)
  详细解决方案

uva1103 Ancient Messages(dfs)

热度:33   发布时间:2024-01-10 18:47:32.0

每个象形字中有不同数量的空白区域,因此寻找象形字中的空白区域,根据空白区域的数量来判断是哪个象形文字 ,最后

#include<bits/stdc++.h>
using namespace std;
int  map1[250][250];
int h,w;
string s;
int dir[4][2]={-1,0,0,1,1,0,0,-1};
int cnt;
void dfs(int x,int y)
{if(map1[x][y]||map1[x][y]==-1)return;else if(map1[x][y]==0){map1[x][y]=-1;for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx>=0&&xx<=h+1&&yy>=0&&yy<=w*4+1){dfs(xx,yy);}}}}
void dfs1(int x,int y)
{if(map1[x][y]==0){cnt++;dfs(x,y);return;}else if(map1[x][y]==1){map1[x][y]=-1;for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx>0&&xx<=h&&yy>0&&yy<=w*4){dfs1(xx,yy);}}}elsereturn;
}
char n[205];
int main()
{int case1=1;map<char,string>ss;ss['0']="0000";ss['1']="0001";ss['2']="0010";ss['3']="0011";ss['4']="0100";ss['5']="0101";ss['6']="0110";ss['7']="0111";ss['8']="1000";ss['9']="1001";ss['a']="1010";ss['b']="1011";ss['c']="1100";ss['d']="1101";ss['e']="1110";ss['f']="1111";char f[10];f[0]='W';f[1]='A';f[2]='K';f[3]='J';f[4]='S';f[5]='D';while(cin>>h>>w){if(!h&&!w)break;int num=1;memset(map1,0,sizeof(map1));memset(n,0,sizeof(n));for(int i=1;i<=h;i++){cin>>s;int j=0;for(int i=0;i<s.size();i++){char x=s[i];for(int k=0;k<ss[x].size();k++)map1[num][++j]=ss[x][k]-'0';}num++;}dfs(0,0);num=0;for(int i=1;i<=h;i++){for(int j=1;j<=w*4;j++){cnt=0;if(map1[i][j]==1){dfs1(i,j);n[++num]=f[cnt];cnt=0;}}}sort(n+1,n+num+1);cout<<"Case "<<case1<<": ";for(int i=1;i<=num;i++)cout<<n[i];cout<<endl;case1++;}return 0;
}

输出按照升序输出。


  相关解决方案