API tools faq
paste
Advertisement
Dorijanko

Minesweeper Code

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