2015
05-23

# Mahjong

In the 22nd Century, more than one hundred million people attend the Mahjong Sports all over the world. Professional Mahjong players are getting more and more attentions. In many high schools, there’ll be a large-scale Mahjong match every year to select talented students to attend the National Olympiad in Mahjong. For high scores to prove themselves and eager to be a professional Mahjong player someday, students compete with each other for the honor of the Mahjong.
Saki, a girl whose mother and elder sister are professional Mahjong players, will attend the National Olympiad in Mahjong in province (NOMP) this year. To beat other high school, achieve the first prize and attend the National Olympiad in Mahjong (NOM), she and her friends decide to make a camp to train their Mahjong skill.
A very important skill of Mahjong match is to control power of the game. A good Mahjong player could control the game, even all tiles of the game, just like Amae Koromo, whose favorite skill is "catching the moon from the bottom of the sea". This time, Saki and her friends are training their control skill of the Mahjong tiles via the following way.

Saki got a lot of colored Mahjong tiles, and put them into an n * n matrix. Assume there are no more than two Mahjong tiles with the same color. Saki wants to use the Psychic force to control the tiles to the specified state. She could do two kinds of operation as follows:
A. To choose a row arbitrarily, and then swap two tiles’ position in this row. This operation will cost CA magic power.
B. To choose a column arbitrarily, and then swap two tiles’ position in this column. This operation will cost CB magic power.
Moreover, if you do the same kind of operation as you just did, the operation will cost no power. For example, Saki could make operation BAAAAA but just cost CB+CA magic power. Saki wants to know how to do the operations to finish the task with the least cost.

There are several cases.
The first line is an integer T (T < = 20), indicating the test cases.
Each case starts with three integers n, CA, CB, (1<=n<=300, 1<=CA, CB<=10^6). then 2*n*n integer follows, indicating the initial state and the target state of the grid. Each integer Aij(1<=Aij<=10^5) represent a Mahjong tile.

There are several cases.
The first line is an integer T (T < = 20), indicating the test cases.
Each case starts with three integers n, CA, CB, (1<=n<=300, 1<=CA, CB<=10^6). then 2*n*n integer follows, indicating the initial state and the target state of the grid. Each integer Aij(1<=Aij<=10^5) represent a Mahjong tile.

3
3 16 9
2 5 6
1 1 3
7 8 3
2 5 1
3 3 6
7 8 1
2 193 43
1 2
2 1
1 2
2 2
3 10 20
1 2 3
4 5 4
3 2 1
2 1 2
1 5 3
4 3 4

Case #1: 34
Case #2: Take off the shoes!
Case #3: 30

1.不能达到
2.直接等同
3.一步可达
4.两步可达
5.三步可达

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 305;
const int MAXM = 100010;

struct Edge
{
int v, next;
} shift[MAXN*MAXN*2], edge[MAXN*MAXN*4];
int shiftNumber, edgeNumber;

int a[MAXN][MAXN], b[MAXN][MAXN];
int al[MAXN*MAXN], bl[MAXN*MAXN];
int ta[MAXN], tb[MAXN];
int na[MAXM], nb[MAXM];
int pa[MAXM][2], pb[MAXM][2];
bool va[MAXM], vb[MAXM];
int n, nn, ca, cb;
int differ[MAXN*MAXN], differNumber;
int maxNumber;

bool inStack[MAXN*MAXN*2];
int dfn[MAXN*MAXN*2], low[MAXN*MAXN*2];
int stack[MAXN*MAXN*2], belong[MAXN*MAXN*2];
int top, index, componentNumber;

inline int min(int x, int y)
{
return x < y ? x : y;
}

inline int max(int x, int y)
{
return x > y ? x : y;
}

inline void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}

inline int getPosition(int x, int y)
{
return x * n + y;
}

inline int getRow(int pos)
{
return pos / n;
}

inline int getColumn(int pos)
{
return pos % n;
}

void clearEdges()
{
shiftNumber = 0;
edgeNumber = 0;
}

inline void addShift(int u, int v)
{
shift[shiftNumber].v = v;
}

inline void addEdge(int u, int v)
{
edge[edgeNumber].v = v;
}

void transpose()
{
for(int i=0; i<n; ++i)
{
for(int j=i+1; j<n; ++j)
{
swap(a[i][j], a[j][i]);
swap(b[i][j], b[j][i]);
}
}
}

void getDifference()
{
differ[al[0]] = 0;
differNumber = 1;
for(int i=1; i<nn; ++i)
{
if(al[i] != al[i-1])
{
differ[al[i]] = differNumber ++;
}
}
}

void getNumberPosition()
{
memset(na, 0, sizeof(na));
memset(nb, 0, sizeof(nb));
for(int i=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
pa[a[i][j]][na[a[i][j]]++] = getPosition(i, j);
pb[b[i][j]][nb[b[i][j]]++] = getPosition(i, j);
}
}

}

bool isUnreachable()
{
sort(al, al + nn);
sort(bl, bl + nn);
for(int i=0; i<nn; ++i)
{
if(al[i] != bl[i])
{
return true;
}
}
return false;
}

bool isReachableByOneStep()
{
for(int i=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
ta[j] = a[i][j];
tb[j] = b[i][j];
}
sort(ta, ta + n);
sort(tb, tb + n);
for(int j=0; j<n; ++j)
{
if(ta[j] != tb[j])
{
return false;
}
}
}
return true;
}

int myStack[MAXN * MAXN * 8];
int myStackTop;

void push(int x)
{
myStack[myStackTop ++] = x;
}

int pop()
{
return myStack[-- myStackTop];
}

bool isEmpty()
{
return myStackTop == 0;
}

void dfs(int x, int depth)
{
int i, t;
myStackTop = 0;
start:
dfn[x] = low[x] = index ++;
inStack[x] = true;
stack[top++] = x;
{
if(dfn[edge[i].v] == -1)
{
push(x);
push(depth);
push(i);
push(t);
x = edge[i].v;
depth = depth + 1;
goto start;
ret:
low[x] = min(low[x], low[edge[i].v]);
}
else if(inStack[edge[i].v])
{
low[x] = min(low[x] ,dfn[edge[i].v]);
}
}
if(dfn[x] == low[x])
{
do
{
t = stack[--top];
inStack[t] = false;
belong[t] = componentNumber;
}
while(t != x);
++ componentNumber;
}
if(isEmpty())
{
return;
}
t = pop();
i = pop();
depth = pop();
x = pop();
goto ret;
}

void tarjan()
{
memset(inStack, false, sizeof(inStack));
memset(dfn, -1, sizeof(dfn));
memset(low, -1, sizeof(low));
top = index = componentNumber = 0;
for(int i=0; i<differNumber*2; ++i)
{
if(dfn[i] == -1)
{
dfs(i, 0);
}
}
}

bool isReachableByTwoStep()
{
clearEdges();
for(int i=1; i<=maxNumber; ++i)
{
if(na[i] == 1)
{
}
else if(na[i] == 2)
{
}
}
for(int i=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
{
for(int l=shift[k].next; l!=-1; l=shift[l].next)
{
if((shift[k].v ^ 1) == shift[l].v)
{
continue;
}
}
}
}
}
tarjan();
for(int i=0; i<differNumber; ++i)
{
if(belong[i<<1] == belong[(i<<1)+1])
{
return false;
}
}
return true;
}

int main()
{
int caseNumber;
scanf("%d", &caseNumber);
for(int cas=1; cas<=caseNumber; ++cas)
{
scanf("%d%d%d", &n, &ca, &cb);
nn = n * n;
bool isSame = true;
maxNumber = 0;
for(int i=0,k=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
scanf("%d", &a[i][j]);
al[k++] = a[i][j];
maxNumber = max(maxNumber, a[i][j]);
}
}
for(int i=0,k=0; i<n; ++i)
{
for(int j=0; j<n; ++j)
{
scanf("%d", &b[i][j]);
bl[k++] = b[i][j];
if(a[i][j] != b[i][j])
{
isSame = false;
}
}
}
printf("Case #%d: ", cas);
if(isSame)
{
printf("0\n");
}
else
{
if(isUnreachable())
{
printf("Take off the shoes!\n");
}
else
{
int ans = min(ca * 2 + cb, cb * 2 + ca);
if(isReachableByOneStep())
{
ans = ca;
}
transpose();
if(ans > cb)
{
if(isReachableByOneStep())
{
ans = cb;
}
}
if(ans > ca + cb)
{
getDifference();
getNumberPosition();
if(isReachableByTwoStep())
{
ans = ca + cb;
}
else
{
transpose();
getNumberPosition();
if(isReachableByTwoStep())
{
ans = ca + cb;
}
}
}
printf("%d\n", ans);
}
}
}
return 0;
}


1. 要想说就直说，什么天朝天朝的，烦死了。就说当权者怎么了，制度和体制不改革就没有民主，自由，人权。就两极分化，贫富差距，贪污腐败，怨声载道，现状还有文明吗？思维落后不是普通百姓的错，而是现在的制度决定的，没有钱能办事吗？不溜须拍马能有好日子过吗？没有钱能干

2. 要想说就直说，什么天朝天朝的，烦死了。就说当权者怎么了，制度和体制不改革就没有民主，自由，人权。就两极分化，贫富差距，贪污腐败，怨声载道，现状还有文明吗？思维落后不是普通百姓的错，而是现在的制度决定的，没有钱能办事吗？不溜须拍马能有好日子过吗？没有钱能干

3. 要想说就直说，什么天朝天朝的，烦死了。就说当权者怎么了，制度和体制不改革就没有民主，自由，人权。就两极分化，贫富差距，贪污腐败，怨声载道，现状还有文明吗？思维落后不是普通百姓的错，而是现在的制度决定的，没有钱能办事吗？不溜须拍马能有好日子过吗？没有钱能干

4. 要想说就直说，什么天朝天朝的，烦死了。就说当权者怎么了，制度和体制不改革就没有民主，自由，人权。就两极分化，贫富差距，贪污腐败，怨声载道，现状还有文明吗？思维落后不是普通百姓的错，而是现在的制度决定的，没有钱能办事吗？不溜须拍马能有好日子过吗？没有钱能干

5. 要想说就直说，什么天朝天朝的，烦死了。就说当权者怎么了，制度和体制不改革就没有民主，自由，人权。就两极分化，贫富差距，贪污腐败，怨声载道，现状还有文明吗？思维落后不是普通百姓的错，而是现在的制度决定的，没有钱能办事吗？不溜须拍马能有好日子过吗？没有钱能干

6. a货网 Hermes(爱马仕)MiuMiu(缪缪)奇拿(CIENALE)Sotirio Bulgari(宝格丽)philipp plein(菲利普普来因)CéLINE(赛琳)HelmutLangahuo.ml