Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
哎~表示不会高斯消元法,只会位运算。。如果哪位神牛能发一下此题的高斯消元法代码,感激不尽! #include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <stack> #include <vector> using namespace std; char map[5][5]; bool vis[65540]; struct NOTE { int num,rod,last,pre; }; vector<NOTE> q; NOTE tp,dk; void read() { for(int i=0;i<4;i++) scanf("%s",map[i]); } void pretreat() { tp.num=0;tp.rod=0;tp.last=0;tp.pre=-1; for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(map[i][j]=='+') tp.num+=(1<<(4*i+j)); } NOTE bfs() { q.push_back(tp); vis[tp.num]=true; for(int i=0;i<q.size();i++) { NOTE sta=q[i],tmp; tmp.rod=sta.rod+1;tmp.pre=i; if(tmp.rod>16) continue; for(int j=sta.last+1;j<=16;j++) { int ra=sta.num; int x=(j-1)/4; ra=ra^(1<<(x*4)); ra=ra^(1<<(x*4+1)); ra=ra^(1<<(x*4+2)); ra=ra^(1<<(x*4+3)); x=(j-1)%4; ra=ra^(1<<(x)); ra=ra^(1<<(x+4)); ra=ra^(1<<(x+8)); ra=ra^(1<<(x+12)); ra=ra^(1<<(j-1)); tmp.num=ra;tmp.last=j; if(tmp.num==0) { //q.push_back(tmp); printf("%d\n",tmp.rod); return(tmp); } if(!vis[tmp.num]) { vis[tmp.num]=true; q.push_back(tmp); } } } } void print() { stack<NOTE> st; NOTE x=dk; while(x.pre!=-1) { st.push(x); x=q[x.pre]; } while(!st.empty()) { printf("%d %d\n",(st.top().last-1)/4+1,(st.top().last-1)%4+1); st.pop(); } } int main() { read(); pretreat(); if(tp.num==0) { printf("0\n"); return 0; } dk=bfs(); print(); system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator