Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哎~表示不会高斯消元法,只会位运算。。

Posted by proverbs at 2012-05-01 20:30:13 on Problem 2965
如果哪位神牛能发一下此题的高斯消元法代码,感激不尽!

#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator