【HDU 5897 2016 ACM ICPC Asia Regional Shenyang Online F】【アナログ+有向図ゲーム】The Game双将一馬最長優勝時間.cpp

10484 ワード

ライブラリ-DU アナログゲーム-SG関数

The Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 46 Accepted Submission(s): 9
Problem Description
Alice and Bob like playing Chinese Chess. One day they are playing a game: Alice has a

General, Bob has a

General
and a

Horse, they both obey the rules of Chinese Chess, which are:
∙

General
has 4 moving directions,

Horse
has 8 moving directions, but they can't move out of the chess board or their own moving areas. See the picture to get more details:
∙
In some circumstances,

Horse
can't move to all his positions, just as you can see in the picture, it can move to the black positions, but can't move to the red positions:
∙
Two

Generals can eat each other if and only if they have the same y-coordinate and

Horse
is not between them.
(For more information, click
http://https://en.wikipedia.org/wiki/Xiangqi)
One is considered to be the winner only when his enemy's

General
is eaten. Please note that if the game is a tie, Alice is considered to be the winner. If Alice know that she has no chance to win the game at the beginning, she will take the strategy to make the game last more steps. If Alice can't win, Bob want to end the game as soon as possible.
If Alice win the game, output "Lucky guy!", else output "Lose in x steps T.T!", x indicates the number of steps they take (the sum of Alice's and Bob's steps). Suppose they all make best strategies.

Input
7 numbers

x1,y1,x2,y2,x3,y3,p, where:
∙

(x1,y1)indicates the coordinate of the Bob's

Horse

(0≤x1≤9,0≤y1≤8);

∙

(x2,y2)indicates the coordinate of the Bob's

General

(7≤x2≤9,3≤y2≤5);
∙

(x3,y3)indicates the coordinate of the Alice's

General

(0≤x3≤3,3≤y3≤5);
∙

p
indicates the people who moves first, 0 for Alice, 1 for Bob.

Output
If Alice win, output "Lucky guy!"(without quotations), else output “Lose in x steps T.T!”, x indicates the number of steps they take (the sum of Alice's and Bob's steps).

Sample Input

 
   
     5 0 0 9 3 0 3 0 2 6 9 5 2 3 1 0 4 7 3 1 4 0 3 2 7 4 1 3 0 3 2 7 4 1 3 1

Sample Output

 
   
     Lucky guy! Lose in 3 steps T.T! Lucky guy! Lose in 4 steps T.T! Lose in 1 steps T.T! 
     
      
      Hint 
      In sample 1, Alice moves first, she can eat Bob's 
     General directly; In sample 2, Bob move his 
     Horse to $(0,5)$, then wherever Alice move her 
     General, it will be eaten by Bob's 
     Horse, so they take 3 steps in total.

Source

2016 ACM/ICPC Asia Regional Shenyang Online

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template inline void gmin(T1 &a, T2 b) { if (binline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
const int dy1[8] = { -2,-2,-1,-1,1,1,2,2 };
const int dx1[8] = { -1,1,-2,2,-2,2,-1,1 };
const int dy2[8] = { -1,-1,-1,-1,1,1,1,1 };
const int dx2[8] = { -1,1,-1,1,-1,1,-1,1 };
const int dy3[4] = { -1,0,0,1 };
const int dx3[4] = { 0,-1,1,0 };
int f[10][9][10][9][10][9][2];
int out[10][9][10][9][10][9];
struct Q
{
int y1, x1, y2, x2, y3, x3, p;
}; queueq;
// の  が  かどうかをチェック
bool ok1(int y, int x)
{
return y >= 0 && y <= 9 && x >= 0 && x <= 8;
}
//Bobの  が  かどうかを  する
bool ok2(int y, int x)
{
return y >= 7 && y <= 9 && x >= 3 && x <= 5;
}
//Aliceの  が  かどうかをチェックする
bool ok3(int y, int x)
{
return y >= 0 && y <= 2 && x >= 3 && x <= 5;
}
// つの が じかどうかを  する
bool dif(int y1, int x1, int y2, int x2)
{
return y1 != y2 || x1 != x2;
}
// つの   が  かどうかを  する
bool ok(int y1, int x1, int y2, int x2, int y3, int x3)
{
return ok1(y1, x1) && ok2(y2, x2) && ok3(y3, x3)
&& dif(y1, x1, y2, x2) && dif(y1, x1, y3, x3) && dif(y2, x2, y3, x3);
}
//  として、トポロジー out[]が しく  するように、    ごとに1 しか  できないことを  しなければならない。
void failit(int y1, int x1, int y2, int x2, int y3, int x3, int p, int step)
{
if (!ok(y1,x1,y2,x2,y3,x3))return;
if (~f[y1][x1][y2][x2][y3][x3][p])return;
f[y1][x1][y2][x2][y3][x3][p] = step;
q.push({ y1,x1,y2,x2,y3,x3,p });
}
void winit(int y1, int x1, int y2, int x2, int y3, int x3, int p)
{
if (!ok(y1,x1,y2,x2,y3,x3))return;
f[y1][x1][y2][x2][y3][x3][p] = 0;
}
bool attack1(int y1, int x1, int y3, int x3)
{
int y = abs(y1 - y3);
int x = abs(x1 - x3);
return y == 2 && x == 1 || y == 1 && x == 2;
}
bool attack2(int y1, int x1, int y3, int x3)
{
int y = abs(y1 - y3);
int x = abs(x1 - x3);
//   の  と  の  に  
return (y == 0 && x == 1 || y == 1 && x == 0) && ok3(y1, x1);
}
//Aliceの      と    を めて、それを り いた 、  の で ずいつでも  が  している  
void getbegin()
{
for (int y1 = 0; y1 <= 9; ++y1)
{
for (int x1 = 0; x1 <= 8; ++x1)
{
for (int y2 = 7; y2 <= 9; ++y2)
{
for (int x2 = 3; x2 <= 5; ++x2)
{
for (int y3 = 0; y3 <= 2; ++y3)
{
for (int x3 = 3; x3 <= 5; ++x3)
{
if (!ok(y1,x1,y2,x2,y3,x3))continue;
//    で が ん にいないと、  の    になり、 を べることと に べられることはありません
if (x3 == x2)
{
if (x1 != x2 || y1 > y2 || y1 < y3)
{
failit(y1, x1, y2, x2, y3, x3, 1, 1);
winit(y1, x1, y2, x2, y3, x3, 0);
}
}
//  がラインを わせていない  、 に われることと を べることの    がある   があります。
else
{
if (attack1(y1, x1, y3, x3))
{
failit(y1, x1, y2, x2, y3, x3, 1, 1);
}
if (attack2(y1, x1, y3, x3) && x1 != x2)
{
winit(y1, x1, y2, x2, y3, x3, 0);
}
}
}
}
}
}
}
}
}
//    に  したときは、トポロジーbfsなので、Bobは  の    の   がいれば きますが、Aliceは  の    の   が てくるときに きます
//そこでAliceがいつ いているかを るために、Aliceの    な  を  します
void getout()
{
for (int y1 = 0; y1 <= 9; ++y1)
{
for (int x1 = 0; x1 <= 8; ++x1)
{
for (int y2 = 7; y2 <= 9; ++y2)
{
for (int x2 = 3; x2 <= 5; ++x2)
{
for (int y3 = 0; y3 <= 2; ++y3)
{
for (int x3 = 3; x3 <= 5; ++x3)
{
if (!ok(y1,x1,y2,x2,y3,x3))continue;
//ここでAliceの 、  （y 3，x 3）
for (int k = 0; k < 4; ++k)
{
int yy = y3 + dy3[k];
int xx = x3 + dx3[k];
if (!ok(y1,x1,y2,x2,yy,xx))continue;
++out[y1][x1][y2][x2][y3][x3];
}
}
}
}
}
}
}
}
void go()
{
while (!q.empty())
{
int y1 = q.front().y1;
int x1 = q.front().x1;
int y2 = q.front().y2;
int x2 = q.front().x2;
int y3 = q.front().y3;
int x3 = q.front().x3;
int p = q.front().p;
q.pop();
int now = f[y1][x1][y2][x2][y3][x3][p];
if(p==0)// のステップはAliceの 、 のステップ(  ステップ)はBobの 
{
//Bobはステップ が も ない   を  します
// .  
for (int k = 0; k < 8; ++k)
{
int yy = y1 + dy1[k];
int xx = x1 + dx1[k];
int yyy = y1 + dy2[k];
int xxx = x1 + dx2[k];
//  を  するときは   を まないように  
if (ok(yy,xx,y2,x2,y3,x3) && dif(yyy, xxx, y2, x2) && dif(yyy, xxx, y3, x3))
{
failit(yy, xx, y2, x2, y3, x3, p ^ 1, now + 1);
}
}
// .  
for (int k = 0; k < 4; ++k)
{
int yy = y2 + dy3[k];
int xx = x2 + dx3[k];
if (ok(y1,x1,yy,xx,y3,x3))
{
failit(y1, x1, yy, xx, y3, x3, p ^ 1, now + 1);
}
}
}
Else// のステップはBobの 、 のステップ(  ステップ)はAliceの 
{
//aliceは  ステップの   を  します
for (int k = 0; k < 4; ++k)
{
int yy = y3 + dy3[k];
int xx = x3 + dx3[k];
if (ok(y1,x1,y2,x2,yy,xx))
{
if (--out[y1][x1][y2][x2][yy][xx] == 0)
{
failit(y1, x1, y2, x2, yy, xx, p ^ 1, now + 1);
}
}
}
}
}
}
//なぜfの を-1に  するのですか? はただ        をマークしただけです!
void init()
{
MS(f, -1);
getbegin();
getout();
go();
}
int main()
{
//fre();
init();
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
int y1, x1, y2, x2, y3, x3, p;
scanf("%d%d%d%d%d%d%d", &y1, &x1, &y2, &x2, &y3, &x3, &p);
if(!ok(y 1,x 1,y 2,x 2,y 3,x 3))while(1);//    データは ず  であることを す
if (f[y1][x1][y2][x2][y3][x3][p] == 0)puts("Lucky guy!");
else printf("Lose in %d steps T.T!", f[y1][x1][y2][x2][y3][x3][p]);
}
return 0;
}
/*
【trick&&ツッコミ】
 たちが  しなければならない  があります。
2つの が じ に いたら、 ですか。
 はこのような  はきっと こらない。すべての    の  が たちに り げられたからだ。
1,   き  い*1
2,   き  い*2
3,        
4,&()   
5,      き  え*3
6, にオーバーフロー  の  については,  では  できない  があることに  する.
【  】
10*9のボードで
ボブには と がいます
アリスは  だけ
 はwhoが く です(who==0はAliceが に、who==1はBobが に く)
アリスはできるだけ きずってほしい
ボブはできるだけ く
このような  の で、 の  を  させます。
【タイプ】
   ゲーム
【  】
f[10][9][3][3][3][3][3][2]を  して  の  を す( が べられる  な  がある   がある)
この   は90*81*2で、15000  です。
  の[2]はこのステップが の になるかを し、0はAlice 、1はBob である。
 が0の  、Aliceは ず つことを します。そうでない  、 はAliceの     です。
まず、Aliceの  の  を  しなければなりません。チームのトップに ります。
そして たちはアリスの    を すことができます--これらの  を  しません
Alice    1を いた ての  は、Aliceの    である。
このときbfsで  の を めることができます。
【     &&   】
O（   ）
*/

gradle構成

OAuth 2とJWTを使用してマイクロサービスにセキュリティを提供