0
Your rating: None

CodeChef submission 129840 (C++ 4.0.0-8)

CodeChef submission 129840 (C++ 4.0.0-8) plaintext list. Status: TLE, problem J1, contest NOV09. By akhilravidas (Akhil Ravidas), 2009-11-11 00:03:43.
  1. #include <map>
  2. #include <set>
  3. #include <list>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <queue>
  7. #include <stack>
  8. #include <string>
  9. #include <cstdio>
  10. #include <cctype>
  11. #include <vector>
  12. #include <cassert>
  13. #include <iomanip>
  14. #include <string.h>
  15. #include <iostream>
  16. #include <algorithm>
  17. using namespace std;
  18. typedef long long LL;
  19. typedef pair<int,int> PI;
  20. #define _DEBUG 1
  21. #define DEBUG if(_DEBUG)
  22. #define dbg(x) DEBUG{cerr << #x << " -> " << (x) << "\t";}
  23. #define dbge(x) DEBUG{cerr << #x << " -> " << (x) << endl;}
  24. #define CLR(X) memset(X,0,sizeof(X))
  25. int Igrid[9][9];
  26. // Encoding / Decoding functions
  27. inline int Encode(int N, int r, int c) 
  28. { 
  29. 	return N*81 + r*9 + c; 
  30. }
  31.  
  32.  
  33. inline int GetNum(int N) 
  34. { 
  35. 	return N/81; 
  36. }
  37.  
  38.  
  39. inline int GetRow(int N) 
  40. { 
  41. 	return (N/9)%9; 
  42. }
  43.  
  44.  
  45. inline int GetCol(int N) 
  46. { 
  47. 	return N%9; 
  48. }
  49.  
  50.  
  51. inline int GetSq(int N) 
  52. { 
  53. 	return ((GetRow(N)/3)*3) + (GetCol(N)/3); 
  54. }
  55.  
  56.  
  57. inline int GetGridpt(int N) 
  58. { 
  59. 	return GetRow(N)*9 + GetCol(N); 
  60. }
  61.  
  62.  
  63. inline int GetNumRo(int N) 
  64. { 
  65. 	return GetNum(N)*9 + GetRow(N); 
  66. }
  67.  
  68.  
  69. inline int GetNumCol(int N) 
  70. { 
  71. 	return GetNum(N)*9 + GetCol(N); 
  72. }
  73.  
  74.  
  75. inline int GetNumSq(int N) 
  76. { 
  77. 	return GetNum(N)*9 + GetSq(N); 
  78. }
  79.  
  80. namespace ExactCover
  81. {
  82. 	const int inf = 1<<30,MX=1024;
  83. 	struct Node
  84. 	{
  85. 		Node * Left , *Right , *Up , *Down ;
  86. 		Node * Column;
  87. 		int Size;
  88. 		int ID;// RowNo
  89. 		string DBG;
  90. 		int RR , CC;
  91. 	} Root , *RootPtr = &Root, Matrix[MX][MX] , *RoStart[MX];
  92.  
  93. 	void Cover( Node * Col )
  94. 	{
  95. 		Col -> Right -> Left = Col -> Left;
  96. 		Col -> Left -> Right = Col -> Right;
  97. 	
  98. 		for ( Node * nextRo = Col -> Down;nextRo != Col ; nextRo = nextRo -> Down )
  99. 		{
  100. 			for ( Node * nxtRight = nextRo -> Right; nxtRight != nextRo; nxtRight = nxtRight -> Right )
  101. 			{
  102. 				nxtRight -> Down -> Up = nxtRight -> Up;
  103. 				nxtRight -> Up -> Down = nxtRight -> Down;
  104. 				nxtRight -> Column -> Size --;
  105. 			}	
  106. 		}
  107. 	}
  108.  
  109.  
  110. 	void UnCover( Node * Col )
  111. 	{
  112. 		for ( Node * nextRo = Col -> Up;nextRo != Col ; nextRo = nextRo -> Up )
  113. 		{
  114. 			for ( Node * nxtRight = nextRo -> Left; nxtRight != nextRo; nxtRight = nxtRight -> Left )
  115. 			{
  116. 				nxtRight -> Column -> Size ++;
  117. 				nxtRight -> Down -> Up = nxtRight;
  118. 				nxtRight -> Up -> Down = nxtRight;
  119. 			}	
  120. 		}
  121. 		Col -> Right -> Left = Col;
  122. 		Col -> Left -> Right = Col;	
  123. 	}
  124.  
  125. 	int depth,Stk[MX],Top;
  126. 	bool Found;
  127. 	int R,C,Filled;// Common for all 
  128. 	bool Input[MX][MX];
  129. 	void Save()
  130. 	{
  131. 		//dbg(Top);
  132. 		int s;
  133. 		for ( int i=0;i<Top;i++ ) {s=Stk[i];Igrid[GetRow(s)][GetCol(s)] = GetNum(s)+1;}//dbge(Stk[i]);
  134. 	}
  135.  
  136. 	void Search ()
  137. 	{
  138. //		dbge(depth);
  139. 		if ( RootPtr -> Right == RootPtr || depth == 81 - Filled )
  140. 		{
  141. 			Save();
  142. 			Found = true;
  143. 			return;
  144. 		}
  145. 		int best = inf;
  146. 		Node * nextCol=RootPtr  , *bestCol ;
  147. 		while(1)
  148. 		{ 
  149. 			nextCol = nextCol -> Right ; 
  150. 			if ( nextCol == RootPtr ) break;
  151. 			if ( best > nextCol-> Size ) 
  152. 				best = nextCol -> Size , bestCol = nextCol; 
  153. 		} 
  154. 		Cover ( bestCol );
  155. 		for ( Node * nextRo = bestCol -> Down ; nextRo != bestCol; nextRo = nextRo -> Down )
  156. 		{
  157. 			Stk[Top++] = nextRo -> ID;
  158. 			for ( Node * nxtRight = nextRo -> Right; nxtRight != nextRo; nxtRight = nxtRight -> Right ) Cover ( nxtRight -> Column );
  159. 		
  160. 			depth ++;
  161. 			Search();
  162. 			depth --;
  163. 			if ( Found )
  164. 				return;
  165. 			for ( Node * nxtRight = nextRo -> Left; nxtRight != nextRo; nxtRight = nxtRight -> Left ) UnCover ( nxtRight -> Column );
  166. 			Top --;
  167. 		}
  168. 		UnCover ( bestCol );
  169. 	
  170. 	}
  171. 	int nextCol ( int n ){ return n<C-1?n+1:0;}
  172. 	int nextRo( int n ) { return n<R-1?n+1:0;}
  173. 	int prevCol ( int n ) { return n?n-1:C-1;}
  174. 	int prevRo ( int n ) { return n?n-1:R-1;}
  175.  
  176. 	void Construct()
  177. 	{
  178. 		int r,c;
  179. 		for ( int i=0;i<R;i++ )
  180. 		for ( int j=0;j<C;j++ ) if ( Input[i][j] )
  181. 		{
  182. 			Matrix[i][j].RR = i , Matrix[i][j].CC = j;
  183. 			// Construct a node for i,j
  184. 			r=i,c=j;
  185. 			do { c=nextCol(c); } while ( Input[i][c] == 0 );
  186. 			Matrix[i][j].Right = &Matrix[i][c];
  187.  
  188. 			r=i,c=j;
  189. 			do { c=prevCol(c); } while ( Input[i][c] == 0 );
  190. 			Matrix[i][j].Left = &Matrix[i][c];
  191.  
  192. 			r=i,c=j;		
  193. 			do { r=nextRo(r); } while ( Input[r][j] == 0 );
  194. 			Matrix[i][j].Down = &Matrix[r][j];
  195.  
  196. 			r=i,c=j;		
  197. 			do { r=prevRo(r); } while ( Input[r][j] == 0 );
  198. 			Matrix[i][j].Up = &Matrix[r][j];
  199. 		
  200. 			Matrix[i][j].Column = &Matrix[R-1][j];
  201. 			Matrix[i][j].Column -> Size++;
  202. 			Matrix[i][j].ID = i;
  203.  
  204. 			RoStart[i] = &Matrix[i][j];
  205. 		}
  206. 		Root.Right = &Matrix[R-1][0]; Root.Left = &Matrix[R-1][C-1];
  207. 		Matrix[R-1][0].Left = &Root; Matrix[R-1][C-1].Right = &Root;
  208. 	}
  209.  
  210.  
  211. /*
  212. 	void init()
  213. 	{
  214. 		scanf("%d %d",&R,&C);
  215. 		for ( int i=0;i<R;i++ ) 
  216. 		for ( int j=0;j<C;j++ )
  217. 			scanf("%d",&Input[i][j]);
  218. 		for ( int i=0;i<C;i++ ) Input[R][i] = 1;
  219. 		R ++;
  220. 	}
  221. */
  222.  
  223. 	void Place ( int num , int r , int c )
  224. 	{
  225. 		int En = Encode ( num , r , c );
  226. 		Node * PresRow = ExactCover::RoStart[En];
  227. 		Cover ( PresRow -> Column );
  228. 		for ( Node * nxtRight = PresRow -> Right; nxtRight != PresRow ; nxtRight = nxtRight -> Right ) 
  229. 			Cover ( nxtRight -> Column );
  230. 		Filled ++;
  231. 		Stk[Top++] = En;
  232. 	}
  233. };
  234.  
  235.  
  236. const int offset1 = 81 , offset2 = offset1+81, offset3 = offset2+81, offset4 = offset3+81, offset5 = offset4+9;
  237. void init()
  238. {
  239. 	// No of rows -> 
  240. 	int R = 81 * 9,num,C;
  241. 	for ( int i=0;i<9;i++ )
  242. 		for ( int j=0;j<9;j++ )
  243. 			for ( int d=0;d<9;d++ )
  244. 			{
  245. 				// place d at i,j
  246. 				num = Encode(d,i,j);
  247. 				
  248. 				ExactCover::Input[num][GetGridpt(num)] = 1;// one per cell
  249.  
  250. 				ExactCover::Input[num][offset1 + GetNumRo(num)] = 1;
  251.  
  252. 				ExactCover::Input[num][offset2 + GetNumCol(num)] = 1;
  253.  
  254. 				ExactCover::Input[num][offset3 + GetNumSq(num)] = 1;
  255. 				// d1
  256. 				if ( i == j )
  257. 					ExactCover::Input[num][offset4 + d] = 1;
  258. 				if ( i == 8-j )
  259. 					ExactCover::Input[num][offset5 + d] = 1;
  260. 				
  261. 			}
  262. 	C = offset5 + 9;
  263. 	for ( int i=0;i<C;i++ ) ExactCover::Input[R][i] = 1;
  264. 	R ++;
  265. 	ExactCover::R = R , ExactCover :: C = C;
  266. }
  267.  
  268.  
  269.  
  270. void FillValues()
  271. {
  272. 	ExactCover::Filled = 0;
  273. 	for ( int i=0;i<9;i++ )
  274. 		for ( int j=0;j<9;j++ ) if ( Igrid[i][j] )
  275. 			ExactCover::Place ( Igrid[i][j]-1 , i , j );
  276. }
  277.  
  278. char _grid[9][9];
  279. void solve()
  280. {
  281. 	ExactCover::Top = ExactCover:: Found = ExactCover:: Filled = 0;
  282. 	ExactCover::Construct();
  283. 	FillValues();
  284. 	ExactCover::Search();
  285. }
  286.  
  287. int main()
  288. {
  289. 	int kase_;
  290. 	init();
  291. 	//freopen ( "inp" , "r" , stdin );
  292. 	scanf("%d\n",&kase_);
  293. 	while(kase_--)
  294. 	{
  295. 		for ( int i=0;i<9;i++ ) scanf("%s\n",_grid[i]);
  296. 		
  297. 		for ( int i=0;i<9;i++ ) 
  298. 		for ( int j=0;j<9;j++ ) 
  299. 		if ( _grid[i][j] >= '0' ) 
  300. 			Igrid[i][j] = _grid[i][j] - '0';
  301. 		else
  302. 			Igrid[i][j] = 0;
  303.  
  304. //		HumanSolve();
  305. 		solve();
  306. 		for ( int i=0;i<9;i++ , printf("\n") ) 
  307. 		for ( int j=0;j<9;j++ ) printf("%d",Igrid[i][j]);
  308. 		printf("\n");
  309. 	}
  310. 	fflush(stdout);
  311. 	return 0;
  312. }
  313.

Comments