第一個雙廣
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
char change[][10] = {"413526789", "253146789", "152463789", "136425789",
"123746859", "123586479", "123485796", "123469758"};
char end[11];
string sta;
int num;
bool flag = 0;
queue < string > q[2]; // 0 -> zheng 1-> fan
map <string , bool> h[2];
void expend(int type, string ini)
{
char next[10];
for( int i= 0; i< 8; i ++ )
{
for( int j= 0; j< 9; j ++ )
next[j]= ini[ change[i][j]- '0'- 1 ];
next[9]= 0;
if( h[type][next] ) continue;
if( h[1-type][next] )
{
flag = 1;
return;
}
q[type].push(next);
h[type][next] = 1;
}
}
int bfs()
{
int cnt = 0, index, len;
while( !q[0].empty() ) q[0].pop();
while( !q[1].empty() ) q[1].pop();
h[0].clear(); h[1].clear();
sta = "123456789";
h[0][sta] = 1;
h[1][end] = 1;
if(h[0][end]) return 0;
q[0].push(sta);
q[1].push(end);
flag = 0;
string temp;
while( !q[0].empty() || !q[1].empty() )
{
index = 0;
if( q[0].size() > q[1].size() ) index = 1;
if( q[index].size() == 0 ) index = 1 - index;
len = q[index].size();
while(len --)
{
temp = q[index].front();
q[index].pop();
expend(index, temp);
if(flag) break;
}
cnt ++;
if(flag) return cnt;
if(cnt > num) return -1;
}
}
int main()
{
int test = 0;
while(gets(end) != NULL)
{
if( !strcmp(end, "0000000000") ) break;
num = end[0] - '0';
for(int i = 0; i <= 9; i ++) end[i] = end[i + 1];
int ans = bfs();
if(ans < 0 || (ans >0 && num < ans) ) ans = -1;
printf("%d. %d\n", ++test, ans);
}
}
如果使用逆序判重的話當然會跑得更快
#include <iostream>
#include <string>
#include <queue>
using namespace std;
char change[][10] = {"413526789", "253146789", "152463789", "136425789",
"123746859", "123586479", "123485796", "123469758"};
char end[11];
string sta;
int num;
bool flag = 0;
queue < string > q[2]; // 0 -> zheng 1-> fan
bool h[2][370000];
int map(string ss)
{
int hash = 0, base = 1, answer = 0;
for(int i = 0; i < 9; i ++)
{
if(!base) base = 1;
base *= i; hash = 0;
for(int j = 0; j < i; j ++)
if(ss[j] > ss[i]) hash ++;
answer += hash * base;
}
return answer;
}
void expend(int type, string ini)
{
char next[10];
int tmp;
for( int i= 0; i< 8; i ++ )
{
for( int j= 0; j< 9; j ++ )
next[j]= ini[ change[i][j]- '0'- 1 ];
next[9]= 0;
tmp = map(next);
if( h[type][tmp] ) continue;
if( h[1-type][tmp] )
{
flag = 1;
return;
}
q[type].push(next);
h[type][tmp] = 1;
}
}
int bfs()
{
int cnt = 0, index, len;
while( !q[0].empty() ) q[0].pop();
while( !q[1].empty() ) q[1].pop();
memset(h, 0, sizeof(h));
sta = "123456789";
h[0][map(sta)] = 1;
h[1][map(end)] = 1;
if(h[0][map(end)]) return 0;
q[0].push(sta);
q[1].push(end);
flag = 0;
string temp;
while( !q[0].empty() || !q[1].empty() )
{
index = 0;
if( q[0].size() > q[1].size() ) index = 1;
if( q[index].size() == 0 ) index = 1 - index;
len = q[index].size();
while(len --)
{
temp = q[index].front();
q[index].pop();
expend(index, temp);
if(flag) break;
}
cnt ++;
if(flag) return cnt;
if(cnt > num) return -1;
}
}
int main()
{
int test = 0;
while(gets(end) != NULL)
{
if( !strcmp(end, "0000000000") ) break;
num = end[0] - '0';
for(int i = 0; i <= 9; i ++) end[i] = end[i + 1];
int ans = bfs();
if(ans < 0 || (ans >0 && num < ans) ) ans = -1;
printf("%d. %d\n", ++test, ans);
}
}