当前位置: 代码迷 >> 综合 >> uva 1103 Ancient Messages WA
  详细解决方案

uva 1103 Ancient Messages WA

热度:35   发布时间:2023-12-06 08:46:33.0

题目:Ancient Messages


WA,好像是dfs层数太深栈溢出了,不知到怎么解决。


代码:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
using namespace std;int n,m;
string a[500];
char f[10]= {'W','A','K','J','S','D'};
map<char,string> dic;
int M1[5]= {0, 0,1,-1};
int M2[5]= {1,-1,0, 0};
int use[500][500]= {0};
int sum=0;
int sum2=0;void make() {dic['0']="0000";dic['1']="0001";dic['2']="0010";dic['3']="0011";dic['4']="0100";dic['5']="0101";dic['6']="0110";dic['7']="0111";dic['8']="1000";dic['9']="1001";dic['a']="1010";dic['b']="1011";dic['c']="1100";dic['d']="1101";dic['e']="1110";dic['f']="1111";
}void init() {for(int i=0; i<300; i++) a[i].clear();memset(use,0,sizeof(use));sum=0;sum2=1;
}void dfs(int x,int y,char w,int fill) {use[x][y]=fill;for(int i=0; i<4; i++) {int x_=x+M1[i],y_=y+M2[i];if(0<=x_&&x_<=n+1&&0<=y_&&y_<=4*m+1&&a[x_][y_]==w&&!use[x_][y_]) dfs(x_,y_,w,fill);}
}int main() {int T=0;make();while(scanf("%d%d",&n,&m)==2&&n!=0) {init();char pic[300][55]= {0};for(int i=1; i<=n; i++) {scanf("%s",pic[i]);}for(int j=0; j<=4*m+1; j++) {a[0]+='0';a[n+1]+='0';}for(int i=1; i<=n; i++) {a[i]+='0';for(int j=0; j<m; j++) {a[i]+=dic[pic[i][j]];}a[i]+='0';}for(int i=1; i<=n; i++) {for(int j=1; j<=4*m; j++) {if(!use[i][j]&&a[i][j]=='1') {sum++;dfs(i,j,'1',sum);}}}for(int i=1; i<=n; i++) {for(int j=1; j<=4*m; j++) {if(!use[i][j]&&a[i][j]=='0') {sum2++;dfs(i,j,'0',0-sum2);}}}int cnt[10100]= {0};map<int,bool> h[10100];for(int i=1; i<=n; i++) {for(int j=1; j<=4*m; j++) {if(use[i][j]<-1) {for(int k=0; k<4; k++) {int x_=i+M1[k],y_=j+M2[k];if(0<=x_&&x_<=n&&0<=y_&&y_<=4*m&&use[x_][y_]>0&&!h[0-use[i][j]].count(use[x_][y_])) {h[0-use[i][j]][use[x_][y_]]=true;cnt[use[x_][y_]]++;}}}}}printf("Case %d: ",++T);for(int i=1; i<=sum; i++) {for(int j=0; j<6; j++) {if(cnt[i]==j) printf("%c",f[j]);}}printf("\n");}return 0;
}


  相关解决方案