| ||||||||||
| 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