API tools faq
paste
Advertisement
Dorijanko

minesweeper

Dorijanko
Feb 2nd, 2019
218
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.32 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int n,m,p,ej,ei,k,sj,si,un,kn;
  5. string h[101];
  6. string r[101],l[101];
  7. int dx[]={-1,-1,-1,0,0,1,1,1};
  8. int dy[]={-1,0,1,1,-1,-1,0,1};
  9. vector<vector<string> > v;
  10. double c,cee;
  11.  
  12. int kno()
  13. {
  14. int res=0;
  15. for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h[i][j]!='?')
  16. {
  17. ++res;
  18. ei=max(ei,i+1);
  19. ej=max(ej,j+1);
  20. si=min(si,i);
  21. sj=min(sj,j);
  22. }
  23. return res;
  24. }
  25.  
  26. bool ok(int i,int j)
  27. {
  28. return (i>=si && j>=sj && i<ei && j<ej);
  29. }
  30.  
  31. int sir;
  32. bool doe;
  33. string e[101];
  34. int o[101][101];
  35.  
  36. void rek(int i,int j)
  37. {
  38. //cout<<i<<' '<<j<<endl;
  39. if ((clock()-cee)/CLOCKS_PER_SEC>9.5)
  40. {
  41. cout<<0<<endl;
  42. exit(0);
  43. }
  44. if (v.size()>40000) doe=1;
  45. if (doe) return;
  46. if (j==ej)
  47. {
  48. j=sj;
  49. ++i;
  50. }
  51. //if (!ok(i,j)) return;
  52. bool up=1;
  53. for (int k=0;k<8;++k) if (ok(i+dx[k],j+dy[k]) && r[i+dx[k]][j+dy[k]]!='?') up=0;
  54. //if (i>7) cout<<i<<' '<<j<<' '<<ei<<endl;
  55. if ((up/* || un>15*/) && i!=ei && n*m-kn>15)
  56. {
  57. ++sir;
  58. rek(i,j+1);
  59. --sir;
  60. return;
  61. }
  62. //cout<<i<<' '<<j<<endl;
  63. if (i==ei)
  64. {
  65. //cout<<v.size()<<endl;
  66. for (int i=0;i<n;++i)
  67. {
  68. for (int j=0;j<m;++j) o[i][j]=0;
  69. e[i].clear();
  70. }
  71. int mi=0;
  72. for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h[i][j]=='*') ++mi;
  73. //for (int i=0;i<n;++i) cout<<h[i]<<endl;
  74. //cout<<endl;
  75. if (mi!=p && sir==0 && p!=-1) return;
  76. for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h[i][j]=='*') for (int k=0;k<8;++k) if (ok(i+dx[k],j+dy[k])) ++o[i+dx[k]][j+dy[k]];
  77. for (int i=0;i<n;++i) for (int j=0;j<m;++j)
  78. {
  79. if (h[i][j]=='.') e[i].push_back(o[i][j]+'0');
  80. else e[i].push_back(h[i][j]);
  81. }
  82. for (int i=si;i<ei;++i) for (int j=sj;j<ej;++j)
  83. {
  84. if (e[i][j]!='*' && e[i][j]!='?' && o[i][j]!=e[i][j]-'0')
  85. {
  86. /*for (int i=0;i<n;++i) cout<<e[i]<<endl;
  87. for (int i=si;i<ei;++i) for (int j=sj;j<ej;++j) cout<<o[i][j]<<" \n"[j==(m-1)];
  88. cout<<endl;*/
  89. return;
  90. }
  91. }
  92. vector<string> x;
  93. for (int i=0;i<n;++i)
  94. {
  95. //cout<<e[i]<<endl;
  96. x.push_back(e[i]);
  97. }
  98. v.push_back(x);
  99. }
  100. else if (h[i][j]=='?')
  101. {
  102. ++un;
  103. //cout<<i<<' '<<j<<endl;
  104. h[i][j]='.';
  105. bool moz=1;
  106. for (int k=0;k<8;++k) if (ok(i+dx[k],j+dy[k]))
  107. {
  108. int i1=i+dx[k],j1=j+dy[k];
  109. if (h[i1][j1]<'0' || h[i1][j1]>'8') continue;
  110. bool look=1;
  111. int mi=0;
  112. for (int k=0;k<8;++k) if (ok(i1+dx[k],j1+dy[k]))
  113. {
  114. if (h[i1+dx[k]][j1+dy[k]]=='?')
  115. {
  116. look=0;
  117. break;
  118. }
  119. if (h[i1+dx[k]][j1+dy[k]]=='*') ++mi;
  120. }
  121. if (!look) continue;
  122. if (mi!=h[i1][j1]-'0')
  123. {
  124. moz=0;
  125. break;
  126. }
  127. }
  128. if (moz) rek(i,j+1);
  129. h[i][j]='*';
  130. moz=1;
  131. for (int k=0;k<8;++k) if (ok(i+dx[k],j+dy[k]))
  132. {
  133. int i1=i+dx[k],j1=j+dy[k];
  134. if (h[i1][j1]<'0' || h[i1][j1]>'8') continue;
  135. bool look=1;
  136. int mi=0;
  137. for (int k=0;k<8;++k) if (ok(i1+dx[k],j1+dy[k]))
  138. {
  139. if (h[i1+dx[k]][j1+dy[k]]=='?')
  140. {
  141. look=0;
  142. break;
  143. }
  144. if (h[i1+dx[k]][j1+dy[k]]=='*') ++mi;
  145. }
  146. if (!look) continue;
  147. if (mi!=h[i1][j1]-'0')
  148. {
  149. moz=0;
  150. break;
  151. }
  152. }
  153. if (moz) rek(i,j+1);
  154. --un;
  155. h[i][j]='?';
  156. }
  157. else
  158. {
  159. if (h[i][j]>'8' || h[i][j]<'0')
  160. {
  161. rek(i,j+1);
  162. return;
  163. }
  164. int mini=0;
  165. for (int k=0;k<8;++k) if (ok(i+dx[k],j+dy[k]) && h[i+dx[k]][j+dy[k]]=='*') ++mini;
  166. if (mini>h[i][j]-'0') return;
  167. int pos=0;
  168. for (int k=0;k<8;++k) if (ok(i+dx[k],j+dy[k]))
  169. {
  170. pos+=(h[i+dx[k]][j+dy[k]]=='*' || h[i+dx[k]][j+dy[k]]=='?');
  171. }
  172. if (pos<h[i][j]-'0') return;
  173. rek(i,j+1);
  174. //cout<<"Nothing. "<<i<<' '<<j+1<<endl;
  175. }
  176. }
  177.  
  178. int main () {
  179. cin>>n>>m>>k;
  180. cout<<n/2<<' '<<m/2<<endl;
  181. cee=clock();
  182. ej=0;
  183. ei=0;
  184. si=n;
  185. sj=m;
  186. while (1)
  187. {
  188. for (int i=0;i<n;++i)
  189. {
  190. cin>>h[i];
  191. if (h[i]=="Wrong") return 0;
  192. }
  193. for (int i=0;i<n;++i) l[i]=h[i];
  194. if (kno()==n*m) return 0;
  195. un=0;
  196. vector<pair<pair<int,int>,char> > conc;
  197. eas:
  198. //cout<<endl;
  199. //for (int i=0;i<n;++i) cout<<h[i]<<endl;
  200. //cout<<endl;
  201. for (int i=0;i<n;++i) for (int j=0;j<m;++j)
  202. {
  203. int pos=0,que=0;
  204. vector<pair<int,int> > qu;
  205. for (int k=0;k<8;++k) if (i+dx[k]>=0 && i+dx[k]<n && j+dy[k]>=0 && j+dy[k]<m)
  206. {
  207. pos+=(h[i+dx[k]][j+dy[k]]=='*' || h[i+dx[k]][j+dy[k]]=='?');
  208. que+=(h[i+dx[k]][j+dy[k]]=='?');
  209. if (h[i+dx[k]][j+dy[k]]=='?') qu.push_back({i+dx[k],j+dy[k]});
  210. }
  211. if (pos==h[i][j]-'0' && que)
  212. {
  213. for (int k=0;k<8;++k) if (i+dx[k]>=0 && i+dx[k]<n && j+dy[k]>=0 && j+dy[k]<m) if (h[i+dx[k]][j+dy[k]]=='?') h[i+dx[k]][j+dy[k]]='*';
  214. goto eas;
  215. }
  216. if (pos-que==h[i][j]-'0' && que)
  217. {
  218. for (int k=0;k<8;++k) if (i+dx[k]>=0 && i+dx[k]<n && j+dy[k]>=0 && j+dy[k]<m) if (h[i+dx[k]][j+dy[k]]=='?') h[i+dx[k]][j+dy[k]]='.';
  219. goto eas;
  220. }
  221. for (int k=0;k<8;++k) if (i+dx[k]>=0 && i+dx[k]<n && j+dy[k]>=0 && j+dy[k]<m)
  222. {
  223. int i1=i+dx[k],j1=j+dy[k];
  224. if (!(h[i][j]>='0' && h[i][j]<='9') || !(h[i1][j1]>='0' && h[i1][j1]<='9')) continue;
  225. int pos1=0,que1=0;
  226. vector<pair<int,int> > qu1;
  227. for (int k=0;k<8;++k) if (i1+dx[k]>=0 && i1+dx[k]<n && j1+dy[k]>=0 && j1+dy[k]<m)
  228. {
  229. pos1+=(h[i1+dx[k]][j1+dy[k]]=='*' || h[i1+dx[k]][j1+dy[k]]=='?');
  230. que1+=(h[i1+dx[k]][j1+dy[k]]=='?');
  231. if (h[i1+dx[k]][j1+dy[k]]=='?') qu1.push_back({i1+dx[k],j1+dy[k]});
  232. }
  233. int he=h[i][j]-'0'-(pos-que);
  234. int he1=h[i1][j1]-'0'-(pos1-que1);
  235. if (i1==1 && i==1 && j==6 && j1==5)
  236. {
  237. /*cout<<pos<<' '<<que<<' '<<pos1<<' '<<que1<<' '<<he<<' '<<he1<<endl;
  238. for (auto x: qu) cout<<x.first<<' '<<x.second<<endl;
  239. cout<<endl;
  240. for (auto x: qu1) cout<<x.first<<' '<<x.second<<endl;
  241. cout<<endl;*/
  242. }
  243. if (he<he1) continue;
  244. int in=0;
  245. for (auto x: qu) if (find(qu1.begin(),qu1.end(),x)==qu1.end()) ++in;
  246. if (in==0) continue;
  247. if (in==he-he1)
  248. {
  249. for (auto x: qu) if (find(qu1.begin(),qu1.end(),x)==qu1.end()) h[x.first][x.second]='*';
  250. goto eas;
  251. }
  252. if (he==he1 && in)
  253. {
  254. int in1=0;
  255. for (auto x: qu1) if (find(qu.begin(),qu.end(),x)==qu.end()) ++in1;
  256. if (in1) continue;
  257. for (auto x: qu) if (find(qu1.begin(),qu1.end(),x)==qu1.end()) h[x.first][x.second]='.';
  258. goto eas;
  259. }
  260. }
  261. }
  262. for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h[i][j]!=l[i][j]) conc.push_back({{i,j},h[i][j]});
  263. //for (int i=0;i<n;++i) cout<<h[i]<<endl;
  264. if (conc.size())
  265. {
  266. cout<<conc.size()<<endl;
  267. for (auto x: conc)
  268. {
  269. cout<<x.first.first<<' '<<x.first.second<<' '<<x.second<<endl;
  270. h[x.first.first][x.first.second]=x.second;
  271. }
  272. //for (int i=0;i<n;++i) cout<<h[i]<<endl;
  273. continue;
  274. }
  275. //cout<<endl;
  276. //for (int i=0;i<n;++i) cout<<h[i]<<endl;
  277. kn=kno();
  278. doe=0;
  279. for (int i=0;i<n;++i) r[i]=h[i];
  280. if (si || sj || ei-n || ej-m) p=-1;
  281. else p=k;
  282. si=0;
  283. sj=0;
  284. ei=n;
  285. ej=m;
  286. v.clear();
  287. //cout<<si<<' '<<sj<<endl<<ei<<' '<<ej<<endl;
  288. c=clock();
  289. rek(si,sj);
  290. //cout<<si<<' '<<sj<<endl<<ei<<' '<<ej<<endl;
  291. /*for (auto x: v)
  292. {
  293. for (auto y: x) cout<<y<<endl;
  294. cout<<endl;
  295. }*/
  296. for (int i=0;i<n;++i)
  297. {
  298. for (int j=0;j<m;++j)
  299. {
  300. if (l[i][j]!='?') continue;
  301. //cout<<i<<' '<<j<<endl;
  302. if (v[0][i][j]=='?') continue;
  303. char a=v[0][i][j];
  304. for (int k=1;k<v.size();++k) if (v[k][i][j]!=a)
  305. {
  306. a='?';
  307. break;
  308. }
  309. if (a=='?' && v[0][i][j]!='*')
  310. {
  311. a='.';
  312. for (int k=1;k<v.size();++k) if (v[k][i][j]=='*')
  313. {
  314. a='?';
  315. break;
  316. }
  317. }
  318. if (a=='?') continue;
  319. if (a=='*') conc.push_back({{i,j},'*'});
  320. else conc.push_back({{i,j},'.'});
  321. }
  322. }
  323. if (conc.size()==0)
  324. {
  325. int mo[101][101];
  326. for (int i=0;i<n;++i) for (int j=0;j<m;++j) mo[i][j]=0;
  327. for (int i=0;i<n;++i) for (int j=0;j<m;++j)
  328. {
  329. if (l[i][j]!='?') continue;
  330. for (int k=0;k<v.size();++k) if (v[k][i][j]!='*' && v[k][i][j]!='?') ++mo[i][j];
  331. }
  332. int mk=0,ml=0;
  333. for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (mo[i][j]>mo[mk][ml])
  334. {
  335. mk=i;
  336. ml=j;
  337. }
  338. cout<<1<<endl<<mk<<' '<<ml<<" ."<<endl;
  339. continue;
  340. }
  341. cout<<conc.size()<<endl;
  342. for (auto x: conc)
  343. {
  344. cout<<x.first.first<<' '<<x.first.second<<' '<<x.second<<endl;
  345. h[x.first.first][x.first.second]=x.second;
  346. }
  347. //for (int i=0;i<n;++i) cout<<h[i]<<endl;
  348. }
  349. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!