fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int NUM=9;
  27. const int NUMM=22;
  28. const int NUMK=20;
  29.  
  30. const int P[]={1,1<<2,1<<4,1<<6,1<<8,1<<10,1<<12,1<<14,1<<16,1<<18};
  31.  
  32. int n,m,K;
  33. char g[NUMM][NUMM];
  34.  
  35. inline int get(int a,int k)
  36. {
  37. 	return a/P[k]%4;
  38. }
  39.  
  40. inline int revise(int a,int k,int d)
  41. {
  42. 	return a-get(a,k)*P[k]+d*P[k];
  43. }
  44.  
  45. int ma[ 1<<16 ][NUM];
  46. int hash[1<<16];//判断状态合法
  47.  
  48. void update(int& a,int p)//更新
  49. {
  50. 	if(p>0 && ( a==0 || p>a ) )
  51. 		a=p;
  52. }
  53.  
  54. void show(int a)//显示状态
  55. {
  56. 	int i;
  57. 	REP2(i,0,n+1)
  58. 		cout<<get(a,i);
  59. 	cout<<endl;
  60. }
  61.  
  62. int change(string a)//将字符串变成数
  63. {
  64. 	int ans=0;
  65. 	for(int i=n;i>=0;--i)
  66. 		ans=ans*4+a[i]-'0';
  67. 	return ans;
  68. }
  69.  
  70. void pre()//事先计算出所有可能的状态
  71. {
  72. 	int i,j;
  73. 	int st[NUM],top;
  74. 	REP2(i,0,P[n+1])
  75. 	{
  76. 		int num=0;
  77. 		int flag=1;
  78. 		top=0;
  79. 		REP2(j,0,n+1)
  80. 		{
  81. 			int p=get(i,j);
  82. 			if(p==3)
  83. 				++num;
  84. 			else if(p==0)
  85. 				;
  86. 			else if(p==2)
  87. 			{
  88. 				if(top<=0)
  89. 				{
  90. 					flag=0;
  91. 					break;
  92. 				}
  93. 				ma[i][j]=st[--top];
  94. 				ma[i][ma[i][j]]=j;
  95. 			}
  96. 			else st[top++]=j;
  97. 		}
  98. 		if(flag && num<=2 && top==0)
  99. 			hash[i]=1;
  100. 	}
  101. }
  102.  
  103. vector< pair<int,int> > zhuanyi(int i,int j,int oldp,int house,int is)//看拼音知程序
  104. {
  105. 	//并没有考虑地图,仅仅返回所有的转移
  106. 	//Oh No,这道题目比较神，必须保证若两个格子相连，那么这两个点之间必须连边。。。
  107. 	//你只能在S或者T产生两条独立路径或者将路径封闭 用is表示
  108. 	//要求独立插头在端点产生，且端点必须有独立插头
  109. 	int p=oldp,np;
  110. 	int p1=get(p,j-1);
  111. 	int p2=get(p,j);
  112. 	p=revise(p,j-1,0);
  113. 	p=revise(p,j,0);
  114. 	vector< pair<int,int> > ans; 
  115. 	int left=j>=2?get(house,j-2):3;
  116. 	int up=get(house,j);
  117. 	if( ( left==0 && !p1 ) || (up==0 && !p2))//有格子但不相连，否决
  118. 	{
  119. 		if(!p1 && !p2)//如果本身不填还是没事的
  120. 			ans.pb(mp(p,0));
  121. 		return ans;
  122. 	}
  123. 	if(p1==0 && p2==0)
  124. 	{
  125. 		//新增左右匹配的插头
  126. 		np=revise(p,j-1,1);
  127. 		np=revise(np,j,2);
  128. 		if(!is)
  129. 			ans.pb(mp(np,1));
  130. 		//跳过
  131. 		np=p;
  132. 		if(!is)
  133. 			ans.pb(mp(np,0));
  134. 		//新增独立向下的独立插头
  135. 		np=revise(p,j-1,3);
  136. 		if(is)
  137. 			ans.pb(mp(np,1));
  138. 		//新增独立向右的独立插头
  139. 		np=revise(p,j,3);
  140. 		if(is)
  141. 			ans.pb(mp(np,1));
  142. 	}
  143. 	else if(p1!=3 && p2!=3)
  144. 	{
  145. 		if(p1 && p2)//不可能有独立插头
  146. 		{
  147. 			if(p1==p2 && !is)//只能连起来
  148. 			{
  149. 				if(p1==2)
  150. 				{
  151. 					np=revise(p,ma[oldp][j-1],2);
  152. 					ans.pb(mp(np,1));
  153. 				}
  154. 				else if(p1==1)
  155. 				{
  156. 					np=revise(p,ma[oldp][j],1);
  157. 					ans.pb(mp(np,1));
  158. 				}
  159. 			}
  160. 			else if(p1==2 && p2==1 && !is)//可以连起来
  161. 			{
  162. 				np=p;
  163. 				ans.pb(mp(np,1));
  164. 			}
  165. 			else //1,2的话，那么就形成了回路，题目求的是路径,故否决
  166. 			{
  167. 				;
  168. 			}
  169. 		}
  170. 		else
  171. 		{
  172. 			int u=p1?p1:p2;//两种情况似乎可以合并
  173. 			//上面有东西，作为傻叉，我可以将其继续
  174. 			//往下连
  175. 			np=revise(p,j-1,u);
  176. 			if(!is)
  177. 				ans.pb(mp(np,1));
  178. 			//拐了个弯
  179. 			np=revise(p,j,u);
  180. 			if(!is)
  181. 				ans.pb(mp(np,1));
  182. 			//封住
  183. 			if(p2 && is)//往下的封住了
  184. 			{
  185. 				np=revise(p,ma[oldp][j],3);//相连的那个成了可怜的独立插头
  186. 				ans.pb(mp(np,1));
  187. 			}
  188. 			else if(p1 && is)
  189. 			{
  190. 				np=revise(p,ma[oldp][j-1],3);//同上
  191. 				ans.pb(mp(np,1));
  192. 			}
  193. 		}
  194. 	}
  195. 	else //现在肯定有了个独立插头,yy开始
  196. 	{
  197. 		if(p1==3 && p2==3 && !is)//两个独立插头，如果连起来的话就结束算法，找到答案。
  198. 		{
  199. 			if(!p)
  200. 				ans.pb(mp(p,1));
  201. 		}
  202. 		else if(!p1 || !p2)//只有一个独立插头
  203. 		{
  204. 			//首先似乎可以更新答案
  205. 			if(!p && is)//封住了
  206. 				ans.pb(mp(p,1));
  207. 			//然后可以往下或往右拓展
  208. 			//往下连
  209. 			np=revise(p,j-1,3);
  210. 			if(!is)ans.pb(mp(np,1));
  211. 			//拐了个弯
  212. 			np=revise(p,j,3);
  213. 			if(!is)ans.pb(mp(np,1));
  214. 		}
  215. 		else //另一个插头会与独立插头相连，于是修改另一边为独立插头
  216. 		{
  217. 			if(p1==3 && !is)
  218. 			{
  219. 				np=revise(p,ma[oldp][j],3);
  220. 				ans.pb(mp(np,1));
  221. 			}
  222. 			else if(p2==3 && !is)
  223. 			{
  224. 				np=revise(p,ma[oldp][j-1],3);
  225. 				ans.pb(mp(np,1));
  226. 			}
  227. 		}
  228. 	}
  229. 	return ans;
  230. }
  231.  
  232. /*
  233.    x,y
  234.        y   y+1 y+2
  235.    y-2 y-1
  236.    */
  237.  
  238. pair<int,int> getHouse(int x,int y,int old,int what)//更新炮台安放
  239. {
  240. 	//x,y 格子从1开始标号
  241. 	//what 0 路线 1 炮台 2 障碍
  242. 	int num[4]={0,0,0,0};
  243. 	if(y>1)
  244. 	{
  245. 		++num[get(old,y-2)];
  246. 		++num[get(old,y-1)];
  247. 	}
  248. 	++num[get(old,y)];
  249. 	if(y+1<=n)
  250. 		++num[get(old,y+1)];
  251. 	int w=what<2 ? num[!what] : 0;
  252. 	/*
  253. 	cout<<x<<" "<<y<<" "<<what<<endl;
  254. 	show(old);
  255. 	show(revise(old,y-1,what));
  256. 	cout<<endl;
  257. 	*/
  258. 	return mp(revise(old,y-1,what),w);
  259. }
  260.  
  261. map< pair<int,int> ,int > G[NUMK],F[NUMK];
  262. int answer=-100000000;
  263.  
  264. int find(int x)
  265. {
  266. 	int i;
  267. 	REP2(i,0,n+1)
  268. 		if(get(x,i)==0)
  269. 			return 1;
  270. 	return 0;
  271. }
  272.  
  273. void work(int x,int y)
  274. {
  275. 	char p='#';
  276. 	if(y)
  277. 		p=g[x-1][y-1];
  278. 	map< pair<int,int> ,int >::iterator it;
  279. 	int i,j,k;
  280. 	REP(k,0,K)
  281. 	{
  282. 		G[k]=F[k];
  283. 		F[k].clear();
  284. 	}
  285. 	int pp=0;
  286. 	REP2(i,0,n+1)
  287. 		pp=pp*4+2;
  288. 	if(p!='S' && p!='T')F[0][mp(0,pp)]=1;
  289. 	REP(k,0,K)
  290. 		REP2(it,G[k].begin(),G[k].end())
  291. 		{
  292. 			if(!y)
  293. 			{
  294. 				if(get(it->x.x,n)==0)
  295. 					update(F[k][mp(it->x.x*4,revise(it->x.y*4+2,n+1,0))],it->y);
  296. 				continue;
  297. 			}
  298. 			vector< pair<int,int > > ans=zhuanyi(x,y,it->x.x,it->x.y,p=='S' || p=='T');
  299. 			REP2(i,0,3)
  300. 			{
  301. 				if( ( p=='S' || p=='T' ) && i!=0)
  302. 					continue;
  303. 				if(p=='#' && i!=2)
  304. 					continue;
  305. 				REP2(j,0,ans.size())
  306. 				{
  307. 					if(ans[j].y && i!=0)
  308. 						continue;
  309. 					if(!ans[j].y && i==0)
  310. 						continue;
  311. 					int nk=k+(i==1);
  312. 					if(nk>K)continue;
  313. 					int np=ans[j].x;
  314. 					//状态不合法
  315. 					if(hash[np]==0)
  316. 						continue;
  317. 					pair<int,int> nf=getHouse(x,y,it->x.y,i);
  318. 					if(!np)
  319. 					{
  320. 						answer=max(answer,nf.y+it->y);
  321. 						if(!find(nf.x))
  322. 							continue;
  323. 					}
  324. 					update(F[nk][mp(np,nf.x)],nf.y+it->y);
  325. 				}
  326. 			}
  327. 		}
  328. 	/*
  329. 	int sum=0;
  330. 	REP(k,0,K)
  331. 	{
  332. 		sum+=F[k].size();
  333. 		REP2(it,F[k].begin(),F[k].end())
  334. 		{
  335. 			printf("%d %d %d\n",x,y,k);
  336. 			show(it->x.x);
  337. 			show(it->x.y);
  338. 			printf("%d\n",it->y);
  339. 			printf("\n");
  340. 		}
  341. 	}
  342. 	*/
  343. }
  344.  
  345. int main()
  346. {
  347. #ifndef ONLINE_JUDGE
  348. 	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  349. #endif
  350. 	int i,j;
  351. 	scanf("%d%d%d",&m,&n,&K);
  352. 	REP2(i,0,m)
  353. 	{
  354. 		char str[100];
  355. 		scanf("%s",str);
  356. 		REP2(j,0,n)
  357. 			g[i][j]=str[j];
  358. 	}
  359. 	if(n>m)
  360. 	{
  361. 		int temp[NUMM][NUMM];
  362. 		REP2(i,0,m)
  363. 			REP2(j,0,n)
  364. 				temp[j][i]=g[i][j];
  365. 		swap(n,m);
  366. 		REP2(i,0,m)
  367. 			REP2(j,0,n)
  368. 				g[i][j]=temp[i][j];
  369. 	}
  370. 	pre();
  371. 	REP(i,1,m)
  372. 		REP(j,0,n)
  373. 			work(i,j);
  374. 	printf("%d\n",answer-1);
  375. 	return 0;
  376. }
  377.  
Success #stdin #stdout 1.69s 8768KB
comments (?)
stdin
copy 
6 20 15
.......##.........#.
.......#.#........#.
..#.............#...
S#...............##.
..#.......#....#....
..#...........T.....
stdout
copy 
95
https://ideone.com/MLeXMS
language:
C++ (gcc 8.3)
created:
11 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!