| ||||||||||
| 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 | |||||||||
大侠帮看看怎么wa啊#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator