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<iostream> #include<Cstdio> #include<Cstring> #include<stack> using namespace std; struct Node { int x, step; int prev, a1, a2; }; int mark[65536], n; int p[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072}; Node q[65536]; int bfs() { Node cur, next, temp1; int front = 0, end = 1; int temp; if(n == 0) return 0; cur.x = n; cur.step = 0; q[front] = cur; mark[n] = 1; while(front <= end) { cur = q[front++]; for(int i = 0; i < 16; ++i) { next.x = cur.x; next.x = cur.x ^ p[i]; next.a1 = i / 4 + 1; next.a2 = i % 4 + 1; next.prev = front - 1; temp = i + 4; while(temp < 16) { next.x ^= p[temp]; temp += 4; } temp = i - 4; while(temp >= 0) { next.x ^= p[temp]; temp -= 4; } temp = i; if(temp % 4 < 3) { temp ++; while(1) { if(temp % 4 == 3) break; next.x ^= p[temp]; temp ++; } next.x ^= p[temp]; } temp = i; if(temp % 4 > 0) { temp --; while(1) { if(temp % 4 == 0) break; next.x ^= p[temp]; temp --; } next.x ^= p[temp]; } if(next.x == 0) { printf("%d\n",cur.step + 1); temp1 = next; next.step = cur.step + 1; q[end] = next; stack<int> st; st.push(end); while (1) { //cout << temp1.a1 << " " << temp1.a2 << endl; if(q[temp1.prev].step != 0) { st.push(temp1.prev); temp1 = q[temp1.prev]; } if(q[temp1.prev].step == 0) break; } while (!st.empty()) { int pop1 = st.top(); st.pop(); cout << q[pop1].a1 << " " << q[pop1].a2 << endl; } return cur.step + 1; } if(mark[next.x] != 1) { next.step = cur.step + 1; mark[next.x] = 1; q[end++] = next; } } } return -1; } int main() { int i, j, temp; char c; n = 0; for(i = 0; i < 4; i++) { for(j = 0; j < 4; j++) { scanf("%c", &c); temp = i * 4 + j; if(c=='+') n = n + (1 << temp); } getchar(); } 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