ช่วยแกะ code นี้ให้หน่อยนะครับ
ช่วยแกะให้หน่อยนะครับขอวิธีคำนวณก็ได้ครับ คือผมอ่าน code แล้วงงมากๆ
#include<algorithm> #include<bitset> #include<cctype> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<deque> #include<functional> #include<iomanip> #include<iostream> #include<list> #include<map> #include<numeric> #include<queue> #include<set> #include<sstream> #include<stack> #include<string> #include<utility> #include<vector> using namespace std; int rt(int x,vector<int>& fat)//การเรียกโมดูล { if(x==fat[x])/*x เท่ากับ fat[x] หรือไม่ ถ้าใช่ คืนค่า X ถ้าไม่ให้ คืนค่า fat[x] */ return x; else return fat[x]=rt(fat[x],fat); } string check(string s,string pres) {
int c=s.length();
int star=-1; for(int j=0;j<c&&star==-1;j++) if(s[j]=='S') star=j;
vector<int> fat(c); vector<int> pre(10,-1); for(int j=0;j<c;j++) { if(s[j]>='1'&&s[j]<='9') { if(pre[s[j]-'0']==-1) { pre[s[j]-'0']=j; fat[j]=j; } else fat[j]=pre[s[j]-'0']; } else fat[j]=j; } for(int j=0;j<c-1;j++) { if(s[j]=='.'||s[j+1]=='.')continue; int fa=rt(j,fat),fb=rt(j+1,fat); if(fa==fb) return "fuck"; fat[fa]=fb; }
string ret=s; vector<int> bj(c,-1); int newind=1; for(int j=0;j<c;j++) { if(s[j]=='.')continue; int cnn=0; if(j&&s[j-1]!='.')cnn++; if(j!=c-1&&s[j+1]!='.')cnn++; if(pres[j]!='.')cnn++;
if(cnn==1) { int jf=rt(j,fat); if(jf==rt(star,fat)) ret[j]='S'; else if(bj[jf]==-1) { ret[j]='0'+newind; bj[jf]=newind++; } else ret[j]='0'+bj[jf]; } else if(cnn==2) ret[j]='0'; else return "fuck"; }
for(int j=0;j<c-1;j++) if(((ret[j]>='1'&&ret[j]<='9')||ret[j]=='S')&&((ret[j+1]>='1'&&ret[j+1]<='9')||ret[j+1]=='S')) return "fuck"; vector<int> ed(newind,0); for(int j=0;j<c;j++) { if(ret[j]>='1'&&ret[j]<='9') ed[ret[j]-'0']++; } for(int j=1;j<newind;j++) { if(ed[j]!=2) return "fuck"; } return ret; } int main() { int r,c,cas=1; while(cin>>r>>c,(r||c)) { vector<string> mat(r+1,string(c,'.')); for(int i=1;i<=r;i++)cin>>mat[i]; vector<map<string,pair<int,string> > > dp(r+1); dp[0]["S"+string(c-1,'.')].first=0; for(int i=1;i<=r;i++) { for(map<string,pair<int,string> >::iterator it=dp[i-1].begin();it!=dp[i-1].end();it++) { string row=it->first; int num=it->second.first; //cout<<i-1<<" "<<row<<" "<<it->second.second<<endl; string now=string(c,'?'); for(int j=0;j<c;j++) { if(row[j]=='S'||(row[j]>='1'&&row[ j]<='9')) now[j]=row[j]; else if(row[j]=='0') now[j]='.'; } for(int j=0;j<c;j++) { if(j&&row[j]=='0'&&now[j-1]=='?') now[j-1]='.'; if(j!=c-1&&row[j]=='0'&&now[j+1]=='?') now[j+1]='.'; } vector<int> pos; for(int j=0;j<c;j++) { if(now[j]=='?') pos.push_back(j); } int size=pos.size(); for(int s=0;s<(1<<size);s++) { string t=now; for(int j=0;j<size;j++) { if(s&(1<<j)) t[pos[j]]='C'; else t[pos[j]]='.'; } bool contt=0; for(int j=0;!contt&&j<c;j++) if(mat[i][j]=='#'&&t[j]!='.') contt=1; if(contt) continue; t=check(t,row); if(t=="fuck") continue; int tnum=num; for(int j=0;j<c;j++) if(t[j]!='.') tnum++; if(dp[i].find(t)==dp[i].end()||dp[i][t].first<tnum) { dp[i][t].first=tnum; dp[i][t].second=row; } } } } int haha=0; string bst; for(map<string,pair<int,string> >::iterator it=dp[r].begin();it!=dp[r].end();it++) { string row=it->first; int num=it->second.first; int fh=1; for(int j=0;fh&&j<c;j++) if(row[j]>='1'&&row[j]<='9') fh=0; if(fh&&row[c-1]=='S'&&haha<num) { haha=num; bst=row; } } for(int i=r;i>=1;i--) { for(int j=0;j<c;j++) { if(mat[i][j]!='#'&&bst[j]!='.') mat[i][j]='C'; } bst=dp[i][bst].second; } cout<<"Case "<<cas++<<":\n"; for(int i=1;i<=r;i++)cout<<mat[i]<<endl; cout<<endl; } }
|