学步园

贡献一次TLE WA。。。

修改后从170+ms降到了16ms。。。注释写得很清楚。。

萌萌让帮忙改稿子。。不解释了。

#include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <memory.h><br /> using namespace std;<br /> int map[10][10];<br /> int n,k,cou,sum;<br /> void input() //处理输入数据，把能走的赋为0，不能的为2，走过的为1<br /> {<br /> char str[10];<br /> for(int i=1; i<=n; i++)<br /> {<br /> cin >> str;<br /> for(int p=0; p<n; p++)<br /> map[i][p+1] = ( str[p] == '#' ? 0 : 2 );<br /> }<br /> }<br /> int find(int i,int j) //这个函数真应该起个好名字。。。突出不来它的作用捏。。<br /> { // 这个是判断是否有和i j 同行 同列的元素，没的话返回1<br /> for(int p=1; p<=n; p++)<br /> if( map[i][p] == 1 )<br /> return 0;<br /> for(int p=1; p<=n; p++)<br /> if( map[p][j] == 1 )<br /> return 0;<br /> return 1;<br /> }<br /> void DFS(int d) // 深搜呀 深搜呀 深搜。。。<br /> {<br /> if( cou + n - d + 1 < k ) // 这个是如果cou加上未来几行（理想情况下 n-d）+1 还小于K<br /> return ; //即没希望达到K了，早点return。。<br /> if( cou == k )<br /> {<br /> sum++;<br /> return;<br /> }<br /> if( d > n )<br /> return ;<br /> int flag = 0;<br /> for(int j=1; j<=n; j++)<br /> {<br /> if( find(d,j) && !map[d][j] )<br /> {<br /> flag = 1;<br /> map[d][j] = 1;<br /> cou++;<br /> DFS(d+1);<br /> cou--;<br /> map[d][j] = 0;<br /> }<br /> }<br /> if( flag == 1 )<br /> DFS(d+1);<br /> }<br /> int main(void) // 这个不废话了。。 sum记录方案个数，cou记录放置的棋子个数<br /> {<br /> while( cin >> n >> k && n!= -1 )<br /> {<br /> memset( map,0,sizeof(map) );<br /> cou = 0; sum = 0;<br /> input();<br /> DFS(1);<br /> cout << sum << endl;<br /> }<br /> return 0;<br /> }<br />