fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //印出盤面
  4. void print(int r,int c,char data[60][60])
  5. {
  6. 	for(int i=0;i<r;i++)
  7. 	{
  8. 		for(int j=0;j<c;j++)
  9. 		{
  10. 			cout<<data[i][j];
  11. 		}
  12. 		cout<<endl;
  13. 	}
  14. }
  15. //算某個點的上下左右邊位置
  16. vector<pair<int,int> > get8side(int i,int j,int r,int c)
  17. {
  18. 	vector<pair<int,int> > sides;
  19. 	if(i!=0)
  20. 		sides.push_back(make_pair(i-1,j));
  21. 	if(j!=0)
  22. 		sides.push_back(make_pair(i,j-1));
  23. 	if(i<r-1)
  24. 		sides.push_back(make_pair(i+1,j));
  25. 	if(j<c-1)
  26. 		sides.push_back(make_pair(i,j+1));
  27. 	if(i!=0 && j!=0)
  28. 		sides.push_back(make_pair(i-1,j-1));
  29. 	if(i!=0 && j<c-1)
  30. 		sides.push_back(make_pair(i-1,j+1));
  31. 	if(i<r-1 && j!=0)
  32. 		sides.push_back(make_pair(i+1,j-1));
  33. 	if(i<r-1 && j<c-1)
  34. 		sides.push_back(make_pair(i+1,j+1));
  35. 	return sides;
  36. }
  37. //確認這一點的數字是不是0
  38. bool checkZero(int i,int j,int r,int c,char data[60][60])
  39. {
  40. 	if(data[i][j]=='*')
  41. 		return false;
  42. 	vector<pair<int,int> > side=get8side(i,j,r,c);
  43. 	for(int i=0;i<side.size();i++)
  44. 	{
  45. 		if(data[side[i].first][side[i].second]=='*')
  46. 			return 0;
  47. 	}
  48. 	return true;
  49. }
  50. void dfs(int i,int j,int r,int c,char data[60][60],bool visit[60][60])
  51. {
  52. 	if(visit[i][j]==1) return;
  53. 	visit[i][j]=1;
  54. 	if(!checkZero(i,j,r,c,data)) return;
  55. 	vector<pair<int,int> > side=get8side(i,j,r,c);
  56. 	for(vector<pair<int,int> >::iterator iter=side.begin();iter!=side.end();iter++)
  57. 	{
  58. 		dfs(iter->first,iter->second,r,c,data,visit);
  59. 	}
  60. }
  61. //確認盤面是否合理 
  62. bool check(int r,int c,char data[60][60])
  63. {
  64. 	bool visit[60][60]={0};
  65. 	for(int i2=0;i2<r;i2++)
  66. 		for(int j2=0;j2<c;j2++)
  67. 			if(data[i2][j2]=='c')
  68. 			{
  69. 				dfs(i2,j2,r,c,data,visit);
  70. 				for(int i=0;i<r;i++)
  71. 					for(int j=0;j<c;j++)
  72. 					{
  73. 						if(data[i][j]!='*' && visit[i][j]==0){
  74. 							return false;
  75. 						}
  76. 					}
  77. 				return true;
  78. 			}
  79. }
  80. int main()
  81. {
  82. 	int T,no=1;
  83. 	cin>>T;
  84. 	int r,c,m;
  85. 	char data[60][60]; 
  86. 	while(T--)
  87. 	{
  88. 		cin>>r>>c>>m;
  89. 		cout<<"Case #"<<no++<<": "<<endl;
  90. 		memset(data,'.',sizeof data);
  91. 		data[0][0]='c';
  92.  
  93. 		int lr=r-1,lc=c-1;//右下角還沒擺地雷的那個點的座標 
  94. 		//用while迴圈持續放地雷，m帶表剩下的地雷數 
  95. 		while(1)
  96. 		{
  97. 			if(m==0) //全部擺完 
  98. 			{
  99. 				if(check(r,c,data))
  100. 					print(r,c,data);
  101. 				else
  102. 					cout<<"Impossible\n";
  103. 				break;
  104. 			} 
  105. 			else if(m<lr+1 && m<lc+1) //無法擺滿一行 
  106. 			{
  107. 				if(lr+lc-3>=m){
  108. 					for(int i=lc;i>=2;i--){
  109. 						if(m==0)break;
  110. 						data[lr][i]='*';
  111. 						m--;
  112. 					}
  113. 					for(int i=lr-1;i>=2;i--){
  114. 						if(m==0)break;
  115. 						data[i][lc]='*';
  116. 						m--;
  117. 					}
  118. 					if(check(r,c,data))
  119. 						print(r,c,data);
  120. 					else
  121. 						cout<<"Impossible\n";
  122. 				}
  123. 				else
  124. 					cout<<"Impossible\n";
  125. 				break;
  126. 			}
  127. 			//擺右邊及擺下面 
  128. 			else if(lc>lr)
  129. 			{
  130. 				for(int i=0;i<=lr;i++){
  131. 					data[i][lc]='*';
  132. 					m--;
  133. 				}
  134. 				lc--;
  135. 			}
  136. 			else
  137. 			{
  138. 				for(int i=0;i<=lc;i++){
  139. 					data[lr][i]='*';
  140. 					m--;
  141. 				}
  142. 				lr--;
  143. 			}
  144.  
  145. 		}
  146. 	}
  147. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
225
5 2 2
5 4 5
5 5 2
4 2 4
5 3 0
3 5 2
2 3 1
4 3 7
2 2 1
5 4 13
3 5 1
4 4 5
5 5 13
3 2 5
4 1 2
2 2 0
2 3 0
4 5 1
3 2 3
1 3 2
4 5 11
3 5 6
3 5 8
3 5 13
3 5 10
1 1 0
2 3 4
4 3 1
3 5 11
5 5 21
4 1 0
5 4 9
4 5 8
5 4 10
5 5 24
2 5 3
4 5 6
4 4 7
5 5 10
3 5 9
5 1 0
5 5 20
5 4 7
1 5 2
5 2 6
1 5 4
5 5 15
4 2 2
1 4 0
2 3 5
4 5 3
4 3 0
4 5 19
3 3 1
5 5 7
5 3 4
4 5 17
1 5 1
4 4 2
5 5 23
4 3 11
5 3 1
5 5 18
4 2 3
4 1 1
2 4 0
2 4 7
5 3 2
5 4 6
5 5 17
4 5 0
4 4 11
3 3 4
3 4 9
5 5 22
4 4 0
2 4 6
3 2 4
2 4 2
2 1 1
5 3 14
5 5 12
4 3 4
3 5 12
2 4 5
5 3 11
5 4 18
5 4 8
4 5 14
5 5 9
4 3 10
3 3 6
3 3 2
4 4 6
4 3 8
2 5 8
4 3 9
4 4 15
3 5 4
1 4 3
1 5 3
5 5 19
4 5 4
5 4 3
5 4 11
5 2 4
5 1 1
1 5 0
5 5 16
5 2 7
5 5 0
5 1 2
5 1 4
5 5 5
5 5 1
3 3 0
3 4 1
4 4 8
3 5 14
4 5 13
2 5 2
4 4 9
5 5 8
5 4 17
4 1 3
3 4 8
3 4 4
4 5 18
3 3 3
5 5 6
5 1 3
4 3 3
5 3 6
3 1 2
4 5 16
4 2 6
2 5 5
1 4 1
4 5 10
4 3 2
3 3 8
3 4 3
3 2 1
4 5 7
2 4 4
1 3 0
5 3 7
5 4 4
4 5 5
5 3 5
4 4 4
4 2 0
1 4 2
4 5 2
2 5 0
4 4 10
5 2 9
5 2 8
5 4 19
4 2 1
3 1 0
2 1 0
2 3 2
5 3 9
3 2 0
4 5 15
5 4 0
3 4 11
3 5 7
3 3 7
4 4 14
4 5 12
4 4 3
5 4 12
2 5 4
5 3 10
2 5 7
2 2 3
2 2 2
3 4 7
5 5 11
2 5 1
5 3 12
3 5 5
4 2 5
3 5 3
5 4 14
3 4 0
2 5 9
5 2 3
4 2 7
3 5 0
5 3 13
4 4 12
2 5 6
2 4 3
3 4 2
5 5 4
5 5 14
4 4 1
3 3 5
5 5 3
2 3 3
5 2 0
5 2 1
1 2 1
4 5 9
3 4 10
5 3 8
3 2 2
5 3 3
5 2 5
3 4 5
5 4 2
5 4 15
2 4 1
3 1 1
4 4 13
1 2 0
5 4 1
1 3 1
4 3 6
5 4 16
3 4 6
4 3 5
stdout
copy 
Case #1: 
c.
..
..
..
**
Case #2: 
c...
....
....
...*
****
Case #3: 
c....
.....
.....
.....
...**
Case #4: 
c.
..
**
**
Case #5: 
c..
...
...
...
...
Case #6: 
c....
.....
...**
Case #7: 
Impossible
Case #8: 
Impossible
Case #9: 
Impossible
Case #10: 
Impossible
Case #11: 
c....
.....
....*
Case #12: 
c...
....
...*
****
Case #13: 
c...*
....*
....*
*****
*****
Case #14: 
c*
**
**
Case #15: 
c
.
*
*
Case #16: 
c.
..
Case #17: 
c..
...
Case #18: 
c....
.....
.....
....*
Case #19: 
Impossible
Case #20: 
c**
Case #21: 
c..**
...**
...**
*****
Case #22: 
c..**
...**
...**
Case #23: 
Impossible
Case #24: 
Impossible
Case #25: 
Impossible
Case #26: 
c
Case #27: 
Impossible
Case #28: 
c..
...
...
..*
Case #29: 
c.***
..***
*****
Case #30: 
c.***
..***
*****
*****
*****
Case #31: 
c
.
.
.
Case #32: 
c...
....
...*
****
****
Case #33: 
c...*
....*
....*
*****
Case #34: 
c...
....
..**
****
****
Case #35: 
c****
*****
*****
*****
*****
Case #36: 
Impossible
Case #37: 
c...*
....*
....*
..***
Case #38: 
c..*
...*
...*
****
Case #39: 
c...*
....*
....*
...**
*****
Case #40: 
c..**
...**
*****
Case #41: 
c
.
.
.
.
Case #42: 
Impossible
Case #43: 
c...
....
...*
..**
****
Case #44: 
c..**
Case #45: 
c.
..
**
**
**
Case #46: 
c****
Case #47: 
c...*
....*
..***
*****
*****
Case #48: 
c.
..
..
**
Case #49: 
c...
Case #50: 
c**
***
Case #51: 
c....
.....
.....
..***
Case #52: 
c..
...
...
...
Case #53: 
c****
*****
*****
*****
Case #54: 
c..
...
..*
Case #55: 
c....
.....
.....
...**
*****
Case #56: 
c..
...
...
..*
***
Case #57: 
Impossible
Case #58: 
c...*
Case #59: 
c...
....
....
..**
Case #60: 
Impossible
Case #61: 
c**
***
***
***
Case #62: 
c..
...
...
...
..*
Case #63: 
Impossible
Case #64: 
Impossible
Case #65: 
c
.
.
*
Case #66: 
c...
....
Case #67: 
c***
****
Case #68: 
c..
...
...
..*
..*
Case #69: 
c...
....
....
..**
****
Case #70: 
c..**
...**
..***
*****
*****
Case #71: 
c....
.....
.....
.....
Case #72: 
Impossible
Case #73: 
Impossible
Case #74: 
Impossible
Case #75: 
Impossible
Case #76: 
c...
....
....
....
Case #77: 
Impossible
Case #78: 
Impossible
Case #79: 
c..*
...*
Case #80: 
c
*
Case #81: 
c**
***
***
***
***
Case #82: 
c...*
....*
...**
..***
*****
Case #83: 
c..
...
..*
***
Case #84: 
Impossible
Case #85: 
Impossible
Case #86: 
c.*
..*
***
***
***
Case #87: 
Impossible
Case #88: 
c...
....
....
****
****
Case #89: 
c..**
...**
*****
*****
Case #90: 
c...*
....*
....*
....*
*****
Case #91: 
Impossible
Case #92: 
Impossible
Case #93: 
Impossible
Case #94: 
c...
....
..**
****
Case #95: 
c.*
..*
***
***
Case #96: 
Impossible
Case #97: 
Impossible
Case #98: 
c***
****
****
****
Case #99: 
c...*
....*
...**
Case #100: 
c***
Case #101: 
c.***
Case #102: 
c..**
...**
*****
*****
*****
Case #103: 
c...*
....*
....*
....*
Case #104: 
c...
....
....
...*
..**
Case #105: 
c..*
...*
...*
****
****
Case #106: 
c.
..
..
**
**
Case #107: 
c
.
.
.
*
Case #108: 
c....
Case #109: 
c..**
...**
...**
*****
*****
Case #110: 
Impossible
Case #111: 
c....
.....
.....
.....
.....
Case #112: 
c
.
.
*
*
Case #113: 
c
*
*
*
*
Case #114: 
c....
.....
.....
.....
*****
Case #115: 
c....
.....
.....
.....
....*
Case #116: 
c..
...
...
Case #117: 
c...
....
...*
Case #118: 
c..*
...*
..**
****
Case #119: 
c****
*****
*****
Case #120: 
Impossible
Case #121: 
c...*
....*
Case #122: 
Impossible
Case #123: 
c....
.....
.....
..***
*****
Case #124: 
Impossible
Case #125: 
c
*
*
*
Case #126: 
c.**
..**
****
Case #127: 
c..*
...*
..**
Case #128: 
Impossible
Case #129: 
c..
...
***
Case #130: 
c....
.....
.....
....*
*****
Case #131: 
c
.
*
*
*
Case #132: 
c..
...
...
***
Case #133: 
c..
...
...
***
***
Case #134: 
c
*
*
Case #135: 
c.***
..***
*****
*****
Case #136: 
Impossible
Case #137: 
Impossible
Case #138: 
c..*
Case #139: 
c...*
....*
..***
*****
Case #140: 
c..
...
..*
..*
Case #141: 
c**
***
***
Case #142: 
c..*
...*
...*
Case #143: 
Impossible
Case #144: 
c...*
....*
...**
..***
Case #145: 
c.**
..**
Case #146: 
c..
Case #147: 
c..
...
..*
***
***
Case #148: 
c...
....
....
....
****
Case #149: 
c...*
....*
....*
...**
Case #150: 
c..
...
..*
..*
***
Case #151: 
c...
....
....
****
Case #152: 
c.
..
..
..
Case #153: 
c.**
Case #154: 
c....
.....
.....
...**
Case #155: 
c....
.....
Case #156: 
c..*
...*
****
****
Case #157: 
c*
**
**
**
**
Case #158: 
Impossible
Case #159: 
c***
****
****
****
****
Case #160: 
Impossible
Case #161: 
c
.
.
Case #162: 
c
.
Case #163: 
c.*
..*
Case #164: 
c..
...
***
***
***
Case #165: 
c.
..
..
Case #166: 
Impossible
Case #167: 
c...
....
....
....
....
Case #168: 
c***
****
****
Case #169: 
c..**
...**
..***
Case #170: 
Impossible
Case #171: 
Impossible
Case #172: 
c..**
...**
..***
*****
Case #173: 
c...
....
...*
..**
Case #174: 
c..*
...*
..**
****
****
Case #175: 
c..**
...**
Case #176: 
Impossible
Case #177: 
Impossible
Case #178: 
c*
**
Case #179: 
Impossible
Case #180: 
Impossible
Case #181: 
c...*
....*
....*
..***
*****
Case #182: 
Impossible
Case #183: 
Impossible
Case #184: 
c...*
....*
..***
Case #185: 
Impossible
Case #186: 
c...*
....*
....*
Case #187: 
c..*
...*
****
****
****
Case #188: 
c...
....
....
Case #189: 
c****
*****
Case #190: 
Impossible
Case #191: 
c*
**
**
**
Case #192: 
c....
.....
.....
Case #193: 
Impossible
Case #194: 
c.**
..**
****
****
Case #195: 
c.***
..***
Case #196: 
Impossible
Case #197: 
c...
....
..**
Case #198: 
c....
.....
.....
....*
..***
Case #199: 
c...*
....*
...**
*****
*****
Case #200: 
c...
....
....
...*
Case #201: 
c.*
..*
***
Case #202: 
c....
.....
.....
.....
..***
Case #203: 
Impossible
Case #204: 
c.
..
..
..
..
Case #205: 
Impossible
Case #206: 
c*
Case #207: 
c...*
....*
...**
*****
Case #208: 
Impossible
Case #209: 
Impossible
Case #210: 
c.
..
**
Case #211: 
c..
...
...
...
***
Case #212: 
Impossible
Case #213: 
Impossible
Case #214: 
c...
....
....
....
..**
Case #215: 
Impossible
Case #216: 
Impossible
Case #217: 
c
.
*
Case #218: 
Impossible
Case #219: 
c.
Case #220: 
c...
....
....
....
...*
Case #221: 
c.*
Case #222: 
c..
...
***
***
Case #223: 
c.**
..**
****
****
****
Case #224: 
c..*
...*
****
Case #225: 
Impossible
https://ideone.com/sSwi90
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

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!