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