fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <cstring>
  7. #define pb push_back
  8. #define mp make_pair
  9. #define fi first
  10. #define sc second
  11. #define KING 'n'
  12. #define QUEEN 'e'
  13. #define ROOK 'o'
  14. #define BISHOP 's'
  15. #define KNIGHT 'i'
  16. #define PAWN 'w'
  17. #define N 66             //max number of vertices in one part
  18. #define INF 100000000    //just infinity
  19. using namespace std;
  20. void GetStr(char* res){
  21.     char c;
  22.     while(1){
  23.         c=getchar_unlocked();
  24.         if(c==' ' || c=='\n') continue;
  25.         else break;
  26.     }
  27.     *res=c; res++;
  28.     while(1){
  29.         c=getchar_unlocked();
  30.         if (c==' ' || c=='\n' || c==EOF) break;
  31.         *res=c; res++;
  32.     }
  33.     *res='\0';
  34. }
  35.  
  36. int GetInt(){
  37.     int r=0;
  38.     char c;
  39.     while(1){
  40.         c=getchar_unlocked();
  41.         if(c==' ' || c=='\n') continue;
  42.         else break;
  43.     }
  44.     r=c-'0';
  45.     while(1){
  46.         c=getchar_unlocked();
  47.         if(c>='0' && c<='9') r=10*r+c-'0';
  48.         else break;
  49.     }
  50.     return r;
  51. }
  52.  
  53. vector <pair<int, int> > knightStep,bishopStep[4],listMagic;
  54.  
  55. queue < pair <int,int> > q;
  56. int cost[N][N];          	//cost matrix
  57. int n, max_match;        	//n workers and n jobs
  58. int lx[N], ly[N];        	//labels of X and Y parts
  59. int xy[N];               	//xy[x] - vertex that is matched with x,
  60. int yx[N];               	//yx[y] - vertex that is matched with y
  61. bool S[N], T[N];         	//sets S and T in algorithm
  62. int slack[N];            	//as in the algorithm description
  63. int slackx[N];           	//slackx[y] such a vertex, that
  64.                          	// l(slackx[y]) + l(y) - w(slackx[y],y) = slack[y]
  65. int _PREV[N];             	//array for memorizing alternating paths
  66.  
  67. int ans_cost,ans_tile;
  68.  
  69. void initStep(){
  70.  
  71. 	bishopStep[1].pb(mp(1,1));// 4'clock 
  72. 	bishopStep[1].pb(mp(2,2));
  73. 	bishopStep[1].pb(mp(3,3));
  74. 	bishopStep[1].pb(mp(4,4));
  75. 	bishopStep[1].pb(mp(5,5));
  76. 	bishopStep[1].pb(mp(6,6));
  77. 	bishopStep[1].pb(mp(7,7));
  78. 	bishopStep[1].pb(mp(8,8));
  79. 	bishopStep[0].pb(mp(-1,-1)); //10'clock
  80. 	bishopStep[0].pb(mp(-2,-2));
  81. 	bishopStep[0].pb(mp(-3,-3));
  82. 	bishopStep[0].pb(mp(-4,-4));
  83. 	bishopStep[0].pb(mp(-5,-5));
  84. 	bishopStep[0].pb(mp(-6,-6));
  85. 	bishopStep[0].pb(mp(-7,-7));
  86. 	bishopStep[0].pb(mp(-8,-8));
  87. 	bishopStep[3].pb(mp(1,-1));// 7'clock 
  88. 	bishopStep[3].pb(mp(2,-2));
  89. 	bishopStep[3].pb(mp(3,-3));
  90. 	bishopStep[3].pb(mp(4,-4));
  91. 	bishopStep[3].pb(mp(5,-5));
  92. 	bishopStep[3].pb(mp(6,-6));
  93. 	bishopStep[3].pb(mp(7,-7));
  94. 	bishopStep[3].pb(mp(8,-8));
  95. 	bishopStep[2].pb(mp(-1,1)); //1'clock
  96. 	bishopStep[2].pb(mp(-2,2));
  97. 	bishopStep[2].pb(mp(-3,3));
  98. 	bishopStep[2].pb(mp(-4,4));
  99. 	bishopStep[2].pb(mp(-5,5));
  100. 	bishopStep[2].pb(mp(-6,6));
  101. 	bishopStep[2].pb(mp(-7,7));
  102. 	bishopStep[2].pb(mp(-8,8));
  103.  
  104. 	knightStep.pb(mp(2,1));
  105. 	knightStep.pb(mp(2,-1));
  106. 	knightStep.pb(mp(-2,1));
  107. 	knightStep.pb(mp(-2,-1));
  108. 	knightStep.pb(mp(1,2));
  109. 	knightStep.pb(mp(1,-2));
  110. 	knightStep.pb(mp(-1,2));
  111. 	knightStep.pb(mp(-1,-2));
  112. }
  113.  
  114. void init_labels()
  115. {
  116.     memset(lx, 0, sizeof(lx));
  117.     memset(ly, 0, sizeof(ly));
  118.     for (int x = 0; x < n; x++)
  119.         for (int y = 0; y < n; y++)
  120.             lx[x] = max(lx[x], cost[x][y]);
  121. }
  122.  
  123. void add_to_tree(int x, int prevx) 
  124. //x - current vertex,prevx - vertex from X before x in the alternating path,
  125. //so we add edges (prevx, xy[x]), (xy[x], x)
  126. {
  127.     S[x] = true;                    //add x to S
  128.     _PREV[x] = prevx;                //we need this when augmenting
  129.     for (int y = 0; y < n; y++)    //update slacks, because we add new vertex to S
  130.         if (lx[x] + ly[y] - cost[x][y] < slack[y])
  131.         {
  132.             slack[y] = lx[x] + ly[y] - cost[x][y];
  133.             slackx[y] = x;
  134.         }
  135. }
  136.  
  137. void update_labels()
  138. {
  139.     int x, y, delta = INF;             //init delta as infinity
  140.     for (y = 0; y < n; y++)            //calculate delta using slack
  141.         if (!T[y])
  142.             delta = min(delta, slack[y]);
  143.     for (x = 0; x < n; x++)            //update X labels
  144.         if (S[x]) lx[x] -= delta;
  145.     for (y = 0; y < n; y++)            //update Y labels
  146.         if (T[y]) ly[y] += delta;
  147.     for (y = 0; y < n; y++)            //update slack array
  148.         if (!T[y])
  149.             slack[y] -= delta;
  150. }
  151.  
  152. void augment()                         //main function of the algorithm
  153. {
  154.     if (max_match == n) return;        //check wether matching is already perfect
  155.     int x, y, root;                    //just counters and root vertex
  156.     int q[N], wr = 0, rd = 0;          //q - queue for bfs, wr,rd - write and read
  157.                                        //pos in queue
  158.     memset(S, false, sizeof(S));       //init set S
  159.     memset(T, false, sizeof(T));       //init set T
  160.     memset(_PREV, -1, sizeof(_PREV));    //init set _PREV - for the alternating tree
  161.     for (x = 0; x < n; x++)            //finding root of the tree
  162.         if (xy[x] == -1)
  163.         {
  164.             q[wr++] = root = x;
  165.             _PREV[x] = -2;
  166.             S[x] = true;
  167.             break;
  168.         }
  169.  
  170.     for (y = 0; y < n; y++)            //initializing slack array
  171.     {
  172.         slack[y] = lx[root] + ly[y] - cost[root][y];
  173.         slackx[y] = root;
  174.     }
  175. 	//second part of augment() function
  176.     while (true)                                                        //main cycle
  177.     {
  178.         while (rd < wr)                                                 //building tree with bfs cycle
  179.         {
  180.             x = q[rd++];                                                //current vertex from X part
  181.             for (y = 0; y < n; y++)                                     //iterate through all edges in equality graph
  182.                 if (cost[x][y] == lx[x] + ly[y] &&  !T[y])
  183.                 {
  184.                     if (yx[y] == -1) break;                             //an exposed vertex in Y found, so
  185.                                                                         //augmenting path exists!
  186.                     T[y] = true;                                        //else just add y to T,
  187.                     q[wr++] = yx[y];                                    //add vertex yx[y], which is matched
  188.                                                                         //with y, to the queue
  189.                     add_to_tree(yx[y], x);                              //add edges (x,y) and (y,yx[y]) to the tree
  190.                 }
  191.             if (y < n) break;                                           //augmenting path found!
  192.         }
  193.         if (y < n) break;                                               //augmenting path found!
  194.  
  195.         update_labels();                                                //augmenting path not found, so improve labeling
  196.         wr = rd = 0;                
  197.         for (y = 0; y < n; y++)        
  198.         //in this cycle we add edges that were added to the equality graph as a
  199.         //result of improving the labeling, we add edge (slackx[y], y) to the tree if
  200.         //and only if !T[y] &&  slack[y] == 0, also with this edge we add another one
  201.         //(y, yx[y]) or augment the matching, if y was exposed
  202.             if (!T[y] &&  slack[y] == 0)
  203.             {
  204.                 if (yx[y] == -1)                                        //exposed vertex in Y found - augmenting path exists!
  205.                 {
  206.                     x = slackx[y];
  207.                     break;
  208.                 }
  209.                 else
  210.                 {
  211.                     T[y] = true;                                        //else just add y to T,
  212.                     if (!S[yx[y]])    
  213.                     {
  214.                         q[wr++] = yx[y];                                //add vertex yx[y], which is matched with
  215.                                                                         //y, to the queue
  216.                         add_to_tree(yx[y], slackx[y]);                  //and add edges (x,y) and (y,
  217.                                                                         //yx[y]) to the tree
  218.                     }
  219.                 }
  220.             }
  221.         if (y < n) break;                                               //augmenting path found!
  222.     }
  223.  
  224.     if (y < n)                                                          //we found augmenting path!
  225.     {
  226.         max_match++;                                                    //increment matching
  227.         //in this cycle we inverse edges along augmenting path
  228.         for (int cx = x, cy = y, ty; cx != -2; cx = _PREV[cx], cy = ty)
  229.         {
  230.             ty = xy[cx];
  231.             yx[cy] = cx;
  232.             xy[cx] = cy;
  233.         }
  234.         augment();                                                      //recall function, go to step 1 of the algorithm
  235.     }
  236. }//end of augment() function
  237.  
  238. int hungarian()
  239. {
  240.     int ret = 0;                      //weight of the optimal matching
  241.     max_match = 0;                    //number of vertices in current matching
  242.     memset(xy, -1, sizeof(xy));    
  243.     memset(yx, -1, sizeof(yx));
  244.     init_labels();                    //step 0
  245.     augment();                        //steps 1-3
  246. 	ans_cost = ans_tile = 0;
  247.     for (int x = 0; x < n; x++) {      //forming answer there
  248. 		if(cost[x][xy[x]]!=-INF){
  249. 			ans_cost -= cost[x][xy[x]];
  250. 			ans_tile ++;
  251. 		}
  252. 	}
  253.     return ret;
  254. }
  255.  
  256. //king n
  257. //queen e
  258. //rook o 
  259. //bishop s
  260. //knight i
  261. //pawn w
  262.  
  263.  
  264. int main(){
  265. 	int magic[N][N],flag[N][N],x,y,p,l,step,_x,_y,t;
  266. 	char type,temp[15];
  267. 	vector < pair<	 int,pair<int,char> > > data;
  268. 	initStep();
  269. 	t=GetInt();
  270. 	//scanf("%d",&t);
  271. 	for(int tt=1;tt<=t;tt++){
  272. 		data.clear();
  273. 		listMagic.clear();
  274. 		memset(magic,-1,sizeof(magic));
  275. 		memset(flag,-1,sizeof(flag));
  276. 		p=GetInt();
  277. 		l=GetInt();
  278. 		for(int i=0;i<p;i++){
  279. 			x=GetInt();
  280. 			y=GetInt();
  281. 			GetStr(temp);
  282. 			data.pb(mp(x,mp(y,temp[2])));
  283. 		}
  284. 		for(int i=0;i<l;i++){
  285. 			x=GetInt();
  286. 			y=GetInt();
  287. 			magic[x][y]=i;
  288. 			listMagic.pb(mp(x,y));
  289. 		}
  290. 		x = max(p,l);
  291. 		n = x;
  292. 		for(int i=0;i<x;i++){
  293. 			for(int j=0;j<x;j++)cost[i][j]=-INF;
  294. 		}
  295. 		for(int i=0;i<3;i++){
  296. 		    for(int j=0;j<5;j++){
  297. 		        printf("Elem [%d][%d] = %d\n", i, j, cost[i][j]);
  298. 		    }
  299. }
  300. 		for(int i=0;i<p;i++){
  301. 			type =  data[i].second.second;
  302. 			x = data[i].first;
  303. 			y = data[i].second.first;
  304. 			if(type==KING){
  305. 				for(int j=0;j<l;j++){
  306. 					_x = abs(x-listMagic[j].fi);
  307. 					_y = abs(y-listMagic[j].sc);
  308. 					cost[i][j] = -(_x + _y-min(_x,_y));
  309. 				}
  310. 			}
  311. 			else if(type==PAWN){
  312. 				for(int j=0;j<l;j++){
  313. 					if(listMagic[j].sc!=y) continue;
  314. 					_x = abs(x-listMagic[j].fi);
  315. 					cost[i][j] = -_x;
  316. 				}
  317. 			}
  318. 			else if(type==ROOK){
  319. 				for(int j=0;j<l;j++){
  320. 					cost[i][j] = 0;
  321. 					if(listMagic[j].sc!=y)cost[i][j]--;
  322. 					if(listMagic[j].fi!=x)cost[i][j]--;
  323. 				}				
  324. 			}
  325. 			else if(type==QUEEN){
  326. 				for(int j=0;j<l;j++){
  327. 					_x = abs(x-listMagic[j].fi);
  328. 					_y = abs(y-listMagic[j].sc);
  329. 					if(_x+_y == 0)cost[i][j] = 0;
  330. 					else if(_x==_y || _x == 0 || _y == 0) cost[i][j] = -1;
  331. 					else cost[i][j] = -2;
  332. 				}
  333. 			}
  334. 			else if(type==BISHOP){
  335. 				for(int j=0;j<l;j++){
  336. 					_x = abs(x-listMagic[j].fi);
  337. 					_y = abs(y-listMagic[j].sc);
  338. 					if(_x+_y == 0)cost[i][j] = 0;
  339. 					else if(_x==_y) cost[i][j] = -1;
  340. 					else  if((_x+_y)%2==0)cost[i][j] = -2;
  341. 				}
  342. 			}
  343. 			else{
  344. 				q.push(mp(x,y));
  345. 				step=0;
  346. 				while(!q.empty()){
  347. 					for(int j=q.size();j--;){
  348. 						x = q.front().first;
  349. 						y = q.front().second;
  350. 						q.pop();
  351. 						if(flag[x][y]!=i){
  352. 							flag[x][y]=i;
  353. 							if(magic[x][y]>=0)
  354. 								cost[i][magic[x][y]] = step*-1;
  355. 								for(int k = 0;k<knightStep.size();k++){
  356. 									_x = x + knightStep[k].fi;
  357. 									_y = y + knightStep[k].sc;
  358. 									if( _x>=1 && _x<=8 && _y>=1 && _y<=8 ){
  359. 										if(flag[_x][_y]!=i){
  360. 											q.push(mp(_x,_y));
  361. 										}
  362. 									}
  363. 								}
  364.  
  365. 						}
  366.  
  367. 					}
  368. 					step++;
  369. 				}
  370. 			}
  371. 			printf("Iteration %d\n", i);
  372. 		for(int i=0;i<3;i++){
  373. 		    for(int j=0;j<5;j++){
  374. 		        printf("Elem [%d][%d] = %d\n", i, j, cost[i][j]);
  375. 		    }
  376. 		}
  377. 		}
  378. 		hungarian();
  379. 		printf("Case %d: Secret reveals after moving %d pieces with minimum number of moves %d.\n",tt,ans_tile,ans_cost);
  380. 	}
  381. 	return 0; 
  382. }
  383.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
3 5
2 8 king
2 8 queen
7 5 bishop
1 1
2 2
3 6
6 3
4 4
stdout
copy 
Elem [0][0] = -100000000
Elem [0][1] = -100000000
Elem [0][2] = -100000000
Elem [0][3] = -100000000
Elem [0][4] = -100000000
Elem [1][0] = -100000000
Elem [1][1] = -100000000
Elem [1][2] = -100000000
Elem [1][3] = -100000000
Elem [1][4] = -100000000
Elem [2][0] = -100000000
Elem [2][1] = -100000000
Elem [2][2] = -100000000
Elem [2][3] = -100000000
Elem [2][4] = -100000000
Iteration 0
Elem [0][0] = -7
Elem [0][1] = -6
Elem [0][2] = -2
Elem [0][3] = -5
Elem [0][4] = -4
Elem [1][0] = -100000000
Elem [1][1] = -100000000
Elem [1][2] = -100000000
Elem [1][3] = -100000000
Elem [1][4] = -100000000
Elem [2][0] = -100000000
Elem [2][1] = -100000000
Elem [2][2] = -100000000
Elem [2][3] = -100000000
Elem [2][4] = -100000000
Iteration 1
Elem [0][0] = -7
Elem [0][1] = -6
Elem [0][2] = -2
Elem [0][3] = -5
Elem [0][4] = -4
Elem [1][0] = -2
Elem [1][1] = -1
Elem [1][2] = -2
Elem [1][3] = -2
Elem [1][4] = -2
Elem [2][0] = -100000000
Elem [2][1] = -100000000
Elem [2][2] = -100000000
Elem [2][3] = -100000000
Elem [2][4] = -100000000
Iteration 2
Elem [0][0] = -7
Elem [0][1] = -6
Elem [0][2] = -2
Elem [0][3] = -5
Elem [0][4] = -4
Elem [1][0] = -2
Elem [1][1] = -1
Elem [1][2] = -2
Elem [1][3] = -2
Elem [1][4] = -2
Elem [2][0] = -2
Elem [2][1] = -2
Elem [2][2] = -100000000
Elem [2][3] = -100000000
Elem [2][4] = -2
Case 1: Secret reveals after moving 3 pieces with minimum number of moves 5.
https://ideone.com/1wC6Cp
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!