| ||||||||||
| 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