UVAOJ11198 | 哈喽哈咯

Written by razrlele 13:01 March 26, 2015

UVA11198

Rujia Liu的神题啊，虽然AC率有40%，但是AC的人数只有两三百个。。随便搞一搞就前150了 Orz。。。

题意就是给一个序列，只有当两个元素异号且绝对值之和是质数才可以移动到彼此的左右边，即ai可以移动到aj的左边或者右边，aj也可以移动到ai的左边或者右边，问最少移动多少次就可以使整个序列递增排列。

用BFS遍历所有情况，然后用set做HASH表除重。。。

感觉自己对BFS和DFS的理解还是不够透彻啊，这个题目这么明显我依旧还是用DFS作死了一下子囧。。。

然后这回还巩固了一下函数对于数组的调用返回。。。唔。。。虽然是很基本的东西，但是偶尔还是会很晕啊。。。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

/********************************************************

* File Name: uvaoj11198.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

* Homepage: https://yueyu.io

* Created Time: Thu 26 Mar 2015 10:10:02 AM CST

******************************************************/

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

set<int> used;

int co;

struct Digit

{

int d[8];

int s;

};

bool checkOk( int digits[8] )

{

for( int i = 0; i < 8; i++ )

if(abs(digits[i]) != i+1)

return false;

return true;

}

bool checkUsed( int digits[8] )

{

int tmp = 0;

for( int i = 0; i < 8; i++ )

tmp = tmp*10 + abs(digits[i]);

if(used.count(tmp))

return false;

used.insert(tmp);

return true;

}

bool okToMove( int a, int b , int digits[8])

{

int tmp = abs(digits[a]) + abs(digits[b]);

if( tmp%2 && tmp != 9 && tmp != 15 && digits[a]*digits[b] < 0 )

return true;

return false;

}

void move(int digits[8], int i, int j, int status) //0 is right

{

int tmp = digits[i];

if(i < j)

{

for( int k = i; k < j; k++ )//move i to j's right

digits[k] = digits[k+1];

digits[j] = tmp;

if(status == 0)

return ;

swap(digits[j], digits[j-1]);//move i to j's left

return ;

}

else

{

for( int k = i; k > j; k-- )

digits[k] = digits[k-1];

digits[j] = tmp;

if(status == 1)

return ;

swap(digits[j], digits[j+1]); //move i to j's right

return ;

}

int bfs( int digits[8] )

{

int tmparray[8];

Digit tmpQ;

memcpy(tmpQ.d, digits, sizeof(int)*8);

tmpQ.s = 0;

queue<Digit> Q;

Q.push(tmpQ);

while(!Q.empty())

{

tmpQ = Q.front();

Q.pop();

if( checkOk( tmpQ.d ) )

return tmpQ.s;

memcpy(tmparray, tmpQ.d, sizeof(int)*8);

if( !checkUsed( tmparray))

continue ;

int tmpint = tmpQ.s;

for(int i = 0; i < 8; i++)

for(int j = 0; j < 8; j++)

{

if(okToMove(i, j, tmparray))

{

memcpy(tmpQ.d, tmparray, sizeof(int)*8);

tmpQ.s = tmpint+1;

move(tmpQ.d, i, j, 0);

Q.push(tmpQ);

memcpy(tmpQ.d, tmparray, sizeof(int)*8);

move( tmpQ.d, i, j, 1 );

Q.push(tmpQ);

}

return -1;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

int numcase = 0;

int digits[8];

while( scanf("%d", &digits[0]) && digits[0] )

{

for( int i = 1; i < 8; i++ )

scanf("%d", &digits[i]);

used.clear();

printf("Case %d: %d\n", ++numcase,bfs( digits ));

}

return 0;

}