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

大侠帮看看怎么wa啊

Posted by Christole at 2009-08-07 22:16:49 on Problem 2965
#include<iostream>
#include<queue>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

#define N 4

bool state[65536];
struct pos{
	int x;
	int y;
};
bool cmp(const pos & m1, const pos & m2) {
    if (m1.x==m2.x)return m1.y<m2.y;    
	return m1.x < m2.x;
}
struct node{//every state of the refrigerator is represented by a node
	bool switches[N][N];
	int step;
	//queue<pos> sq;由于输出要排序,改用vector
	vector<pos> sq;
};
node source;
queue<node> q;
int getNum(bool B[N][N]){//个人觉得这里只要是个与位置一一对应的函数便可以了
    int sum = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++)
            if(B[i][j]) sum += 1;
            else sum <<= 1;//左移操作,将sum值增倍.但这里是干什么的,没看明白
    }
    return sum;
}
void init(){
	//memset(state,0,sizeof(state));//0表示该节点没处理过,这里的处理是指进dui,这句需要C的函数库string.h
	//freopen("read.txt","r",stdin);
	for (int k=0;k<65536;k++)
		state[k]=0;
	char s[4];
	for (int i=0;i<N;i++){
		gets(s);
		for (int j=0;j<N;j++)
			source.switches[i][j]=(s[j]=='+'?1:0);//关是1,开是0
	}
	source.step=0;
	q.push(source);
	int num=getNum(source.switches);
	state[num]=1;//表示source处理过了
}
int check(bool B[N][N]){
	for (int i=0;i<N;i++)
		for (int j=0;j<N;j++)
			if (B[i][j]==1)
				return 0;
	return 1;
}
void change(node &n,int i,int j){
	n.switches[i][j]=!n.switches[i][j];//i,j位置处理三次,相当于一次
	//处理i行和j列
	for (int x=0;x<N;x++)
		n.switches[i][x]=!n.switches[i][x];
	for (int y=0;y<N;y++)
		n.switches[y][j]=!n.switches[y][j];
}
void bfs(){//按层搜索,每层2^(i-1)个节点。首先核对节点是否达到要求,达到则输出,没有达到则将当前节点子节点入队。
	if(!q.empty()){
		node n=q.front();
		q.pop();
		if(check(n.switches)){//达到要求,输出
			cout<<n.step<<endl;
			vector<pos> qq=n.sq;
			/*while(!qq.empty()){
				pos pp=qq.front();
				qq.pop();
				//貌似输出要排序,先小后大
				cout<<pp.x<<" "<<pp.y<<endl;
			}*/
			sort(qq.begin(),qq.end(),cmp);
			for (int i=0;i<qq.size();i++)
				cout<<qq[i].x<<" "<<qq[i].y<<endl;
			return;
		}
		else{
			for (int i=0;i<N;i++)
				for (int j=0;j<N;j++){
					node t=n;
					change(t,i,j);
					int num=getNum(t.switches);
					if (!state[num]){
						t.step++;
						pos p;
						p.x=i+1;
						p.y=j+1;
						t.sq.push_back(p);
						q.push(t);//进队应该在最后!!!
						state[num]=1;
					}
				}
		}
		bfs();
	}
}
int main(){
	init();
	bfs();
	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