0
Your rating: None

CodeChef submission 129395 (C++ 4.0.0-8)

CodeChef submission 129395 (C++ 4.0.0-8) plaintext list. Status: WA, problem J1, contest NOV09. By fun (fun), 2009-11-10 16:29:29.
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. using namespace std;
  6.  
  7. typedef struct abc{
  8. 	int node_row,node_col,node_ele;
  9. }node;
  10.  
  11. bool arr_row[10][10],arr_col[10][10],arr_block[10][10],arr_l_d[10],arr_b_d[10];
  12. int de = 0,global_de=0;
  13. int pref_arr[10][10];
  14. int arr[10][10];
  15. int global_counter=0,global_empty_counter,global_pos;
  16.  
  17. vector <node>myvect;
  18.  
  19. int get_block(int row,int col)
  20. {
  21. 	if (row<=3)
  22. 	{
  23. 		if (col<=3) return 1;
  24. 		if (col<=6) return 2;
  25. 		return 3;
  26. 	}
  27. 	if (row<=6)
  28. 	{
  29. 		if (col<=3) return 4;
  30. 		if (col<=6) return 5;
  31. 		return 6;
  32. 	}
  33. 	if (col<=3) return 7;
  34. 	if (col<=6) return 8;
  35. 	return 9;
  36. }
  37.  
  38.  
  39. int find_next_ele(int row,int col,int seq,int prev)
  40. {
  41. 	int count = 0;
  42. 	for(int i=prev;i<=9;i++)
  43. 	{
  44. 		if ((arr_row[row][i]==false && arr_col[col][i]==false && arr_block[get_block(row,col)][i]==false)) 
  45. 		{
  46. 			if ((row == col && arr_l_d[i]==false) || row!=col)
  47. 			{
  48. 				if ((row+col==10 && arr_b_d[i]==false) || row+col!=10)
  49. 				{
  50. 					count++;
  51. 					if (count == seq) return i;
  52. 				}
  53. 			}
  54. 		}
  55. 	}
  56. 	return 0;
  57. }
  58.  
  59. void set_prob()
  60. {
  61. 	int count = 0,min = 10,ele,row,col;
  62. 	for(int k=1;k<=9;k++)
  63. 	{
  64. 		row = k;
  65. 		for(int j=1;j<=9;j++)
  66. 		{
  67. 			col = j;
  68. 			if (arr[k][j] != 0) continue;
  69. 			count = 0;
  70. 			for(int i=1;i<=9;i++)
  71. 			{
  72. 				if ((arr_row[row][i]==false && arr_col[col][i]==false && arr_block[get_block(row,col)][i]==false)) 
  73. 				{
  74. 					if ((row == col && arr_l_d[i]==false) || row!=col)
  75. 					{
  76. 						if ((row+col==10 && arr_b_d[i]==false) || row+col!=10)
  77. 						{
  78. 							//							ele = i;			
  79. 							count++;
  80. 						}
  81. 					}
  82. 				}
  83. 			}
  84. 			
  85. 			//			if (pref_arr[row][col] != count){
  86. 			//				if (global_de){
  87. 			//					cout << "not equal row,col,earlier_val,new_val"<<row << col << pref_arr[row][col] << count <<  endl;
  88. 			//				}
  89. 			pref_arr[row][col] = count;
  90. 			node shm; shm.node_row = k; shm.node_col = j;
  91. 			myvect.push_back(shm);
  92. 			//			}
  93. 		}
  94. 	}
  95. }
  96.  
  97.  
  98. node find_min_prob(int seq)
  99. {
  100. 	node as;
  101. 	int count = 0,min = 10,ele,row=0,col=0,r,c;
  102.  
  103. /*	for(int i=1;i<=9;i++)
  104. 	{
  105. 		for(int j=1;j<=9;j++)
  106. 		{
  107. 			if (pref_arr[i][j] < min && pref_arr[i][j]>0 && arr[i][j]==0)
  108. 			{
  109. 				min = pref_arr[i][j];
  110. 				row = i;
  111. 				col = j;
  112. 				if (min == 1) { i= 12; break;}
  113. 			}
  114. 		}
  115. 	}*/
  116. 	for(int i=global_empty_counter;i<myvect.size();i++){
  117. 		as = myvect[i]; row = as.node_row ; col = as.node_col;
  118. 		if (pref_arr[row][col] < min){
  119. 			r = row; c = col; min = pref_arr[r][c];global_pos = i;
  120. 		}
  121. 	}
  122. 	as.node_row = r;
  123. 	as.node_col = c;
  124. 	myvect[global_pos].node_col = myvect[global_empty_counter].node_col;
  125. 	myvect[global_pos].node_row = myvect[global_empty_counter].node_row;
  126.  
  127. 	myvect[global_empty_counter].node_row = r;
  128. 	myvect[global_empty_counter].node_col = c;
  129. 	global_pos = global_empty_counter++;
  130.  
  131. 	as.node_ele = find_next_ele(r,c,seq,1);
  132. 	return as;
  133. }
  134.  
  135. void set_bool(int row,int col,bool bo,int ele)
  136. {
  137. 	arr_row[row][ele] = bo;
  138. 	arr_col[col][ele] = bo;
  139. 	arr_block[get_block(row,col)][ele] = bo;
  140. 	if (row == col) arr_l_d[ele] = bo;
  141. 	if (row + col == 10) arr_b_d[ele] = bo;
  142. }
  143.  
  144. void update(node as,bool bo)
  145. {
  146. 	int row = as.node_row,col = as.node_col,ele = as.node_ele;
  147. 	node shm;
  148. 	if (bo == false)
  149. 	{
  150. 		global_empty_counter--;
  151. 		arr_row[row][ele] = bo; 
  152. 		arr_col[col][ele] = bo;
  153. 		arr_block[get_block(row,col)][ele] = bo;
  154. 		if (row == col) arr_l_d[ele] = bo;
  155. 		if (row+col == 10) arr_b_d[ele] = bo;
  156. 	}
  157.  
  158. 	if (bo)	pref_arr[row][col]--;
  159. 	else pref_arr[row][col]++;
  160. 	for(int i=1;i<=9;i++)
  161. 	{
  162.  
  163. 		if (bo)
  164. 		{
  165. 			if (!arr[i][col])
  166. 			{
  167. 				if (!arr_row[i][ele] && !arr_block[get_block(i,col)][ele] && ((i==col && !arr_l_d[ele])|| (i!=col))&& (((i+col==10) && !arr_b_d[ele]) || (i+col!=10))){
  168. 					pref_arr[i][col]--;
  169. 				}
  170. 			}
  171. 			if (!arr[row][i])
  172. 			{
  173. 				if (!arr_col[i][ele] && !arr_block[get_block(row,i)][ele] && ((i==row && !arr_l_d[ele])|| (i!=row))&& (((i+row==10) && !arr_b_d[ele]) || (i+row!=10))){
  174. 					pref_arr[row][i]--;
  175. 				}
  176. 			}
  177. 		}
  178.  
  179.  
  180. 		else {
  181. 			if (!arr[i][col])
  182. 			{
  183. 				if (!arr_row[i][ele] && !arr_block[get_block(i,col)][ele] && ((i==col && !arr_l_d[ele])|| (i!=col))&& (((i+col==10) && !arr_b_d[ele]) || (i+col!=10))){
  184. 					pref_arr[i][col]++;
  185.  
  186. 				}
  187. 			}
  188. 			if (!arr[row][i])
  189. 			{
  190. 				if (!arr_col[i][ele] && !arr_block[get_block(row,i)][ele] && ((i==row && !arr_l_d[ele])|| (i!=row))&& (((i+row==10) && !arr_b_d[ele]) || (i+row!=10))){
  191. 					pref_arr[row][i]++;
  192. 				}
  193. 			}
  194. 		}
  195. 	}
  196. 	int a,start_row,start_col;
  197. 	a = get_block(row,col);
  198. 	start_row = ( (int) ((a-1)/3))*3 + 1;
  199. 	start_col = ( ((a-1)%3)*3 + 1);
  200.  
  201. 	for(int i=start_row;i<=start_row+2;i++)
  202. 	{
  203. 		if (i == row) continue;
  204. 		for(int j=start_col;j<=start_col+2;j++)
  205. 		{
  206. 			if ((j != col) && (!(row==col && i==j)) && (!(row+col==10 && i+j==10)) && (!arr[i][j])) 
  207. 			if (bo){
  208. 				if (!arr_col[j][ele] && !arr_row[i][ele] && ((i==j && !arr_l_d[ele])|| (i!=j))&& (((i+j==10) && !arr_b_d[ele]) || (i+j!=10))){
  209. 					pref_arr[i][j]--;
  210. 				}
  211. 			}
  212. 			else {
  213. 				if (!arr_col[j][ele] && !arr_row[i][ele] && ((i==j && !arr_l_d[ele])|| (i!=j))&& (((i+j==10) && !arr_b_d[ele]) || (i+j!=10))){
  214. 					pref_arr[i][j]++;
  215. 				}
  216. 			}
  217. 		}
  218. 	}
  219.  
  220. 	if (row == col)
  221. 	{
  222. 		for(int i=1;i<=9;i++)
  223. 		{
  224. 			if (arr[i][i]) continue;
  225. 			if (bo){
  226. 				if (!arr_col[i][ele] && !arr_row[i][ele] && (!arr_block[get_block(i,i)][ele]) && (((i+i==10) && !arr_b_d[ele]) || (i+i!=10))){
  227. 					pref_arr[i][i]--;
  228. 				}
  229.  
  230. 			}
  231. 			else {
  232. 				if (!arr_col[i][ele] && !arr_row[i][ele] && (!arr_block[get_block(i,i)][ele]) && (((i+i==10) && !arr_b_d[ele]) || (i+i!=10))){
  233. 					pref_arr[i][i]++;
  234. 				}
  235. 			}
  236. 		}
  237. 	}
  238.  
  239. 	if (row+col == 10)
  240. 	{
  241. 		for(int i=1;i<=9;i++)
  242. 		{
  243. 			if (arr[i][10-i]) 
  244. 				continue;
  245. 			if (bo) {
  246. 				if (!arr_col[10-i][ele] && !arr_row[i][ele] && (!arr_block[get_block(i,10-i)][ele]) && (((i==10-i) && !arr_l_d[ele]) || (i!=10-i))){
  247. 					pref_arr[i][10-i]--;
  248. 				}
  249. 			}
  250. 			else {
  251. 				if (!arr_col[10-i][ele] && !arr_row[i][ele] && (!arr_block[get_block(i,10-i)][ele]) && (((i==10-i) && !arr_l_d[ele]) || (i!=10-i))){
  252. 					pref_arr[i][10-i]++;
  253. 				}
  254. 			}
  255. 		}
  256. 	}
  257. 	if (bo){
  258. 	if (global_empty_counter == global_pos)	global_empty_counter++;
  259. 	arr_row[row][ele] = bo; 
  260. 	arr_col[col][ele] = bo;
  261. 	arr_block[get_block(row,col)][ele] = bo;
  262. 	if (row == col) arr_l_d[ele] = bo;
  263. 	if (row+col == 10) arr_b_d[ele] = bo;
  264. 	}
  265. }
  266.  
  267. int func()
  268. {
  269. 	node as;
  270. 	int p,row,col,ele;
  271. 	int count = 1;
  272. 	if (global_counter == 81) return 1;
  273. 	as = find_min_prob(count);
  274.  
  275. 	if (as.node_ele == 0) 
  276. 	{
  277. 		return 0;
  278. 	}
  279. 	if (as.node_row == 0 && as.node_col == 0) 
  280. 		return 0;
  281.  
  282. 	row = as.node_row; col = as.node_col; ele = as.node_ele;
  283. 	arr[row][col] = as.node_ele;
  284. 	global_counter++;
  285. 	update(as,true);
  286.  
  287. 	while(as.node_ele)
  288. 	{
  289. 		p = func();
  290. 		if (p) return 1;
  291. 		count++;
  292. 		update(as,false);
  293. 		arr[row][col] = 0;
  294. 		global_counter--;
  295.  
  296. 		as.node_ele = find_next_ele(as.node_row,as.node_col,count,as.node_ele);
  297. 		if (as.node_ele == 0) break;
  298. 		arr[row][col] = as.node_ele;
  299. 		update(as,true);
  300. 		global_counter++;
  301.  
  302. 	}
  303. 	return 0;
  304. }
  305.  
  306. int main()
  307. {
  308. 	int cas,l;
  309. 	cin >> cas;
  310. 	for(int l=0;l<cas;l++)
  311. 	{
  312. 		global_counter = 0;global_de=0;
  313.  
  314. 		for(int i=1;i<=9;i++)
  315. 		{
  316. 			for(int j=1;j<=9;j++)
  317. 			{
  318. 				arr_row[i][j] = false;
  319. 				arr_col[i][j] = false;
  320. 				arr_block[i][j] = false;
  321. 			}
  322. 			arr_l_d[i] = false;
  323. 			arr_b_d[i] = false;
  324. 		}
  325.  
  326.  
  327. 		int a;
  328. 		char ch;
  329. 		char str[15];
  330. 		for(int i=1;i<=9;i++)
  331. 		{
  332. 			for(int j=1;j<=9;j++)
  333. 			{
  334. 				cin >> ch;
  335. 				if(ch == '.') arr[i][j] = 0;
  336. 				else 
  337. 				{
  338. 					global_counter++;
  339. 					arr[i][j] = ch - '0';
  340. 					set_bool(i,j,true,arr[i][j]);
  341. 				}
  342. 			}
  343. 		}
  344.  
  345. 		set_prob();
  346. 		if (global_counter != 81)
  347. 			a = func();
  348. 		for(int i=1;i<=9;i++)
  349. 		{
  350. 			for(int j=1;j<=9;j++)
  351. //				printf("%d",arr[i][j]);
  352. 				cout << arr[i][j];
  353. //			printf("\n");
  354. 			cout << endl;
  355. 		}
  356. 		cout << endl;
  357. 	}
  358. }
  359.

Comments