棋盘挑战WriteUp
原题链接:
一个会TLE但是易于理解的源代码:
#include <iostream>
using namespace std;
int n,ans = 0;
const int N = 15;
int path[N];
bool chess[N][N];
/*创建一个二维棋盘数组,初始值为 true
true表示允许放棋子,false表示不允许放棋子。
*/
bool check( int x , int y)
{
for ( int i = 1 ; i <= n ; i ++) //遍历chess的列,如果不允许放棋子返回false
if ( !chess[i][y] ) return false;
for ( int i = 1 ; i <= n ; i ++) //遍历chess的行,如果不允许放棋子返回false
if ( !chess[x][i] ) return false;
for ( int i = 1 ; i <= n ; i ++) //遍历chess的正反对角线,如果不允许放棋子返回false
for ( int j = 1 ; j <= n ; j ++)
if (( !chess[i][j] && x - y == i - j )|| (!chess[i][j] && i + j == x + y))
return false;
return true;
}
void dfs( int x)
{
if ( x > n)
{
ans ++;
if ( ans <= 3)
{
for ( int i = 1 ; i <= n ; i ++)
cout << path[i] << " ";
cout << endl;
}
return;
}
for ( int y = 1 ; y <= n ; y ++)
{
if (check(x, y))
{
path[x] = y;
chess[x][y] = false;
dfs(x + 1);
path[x] = 0;
chess[x][y] = true;
}
}
}
int main()
{
cin >> n;
for ( int i = 1 ; i <= n ; i ++)
for ( int j = 1 ; j <= n ; j ++)
chess[i][j] = true;
dfs(1);
cout << ans;
return 0;
}
TLE截图:
AC源代码:
#include <iostream>
using namespace std;
int n,ans = 0;
const int N = 15;
int path[N];
bool col[N], dg[2 * N], udg[2 * N];
void dfs( int x)
{
if ( x > n)
{
ans ++;
if ( ans <= 3)
{
for ( int i = 1 ; i <= n ; i ++)
cout << path[i] << " ";
cout << endl;
}
return;
}
for ( int y = 1 ; y <= n ; y ++)
{
if (!col[y] && !dg[x + y] && !udg[ x - y + n])
{
path[x] = y;
col[y] = dg[x + y] = udg[ x - y + n] = true;
dfs(x + 1); //向下一层
path[x] = 0; //恢复现场
col[y] = dg[x + y] = udg[ x - y + n] = false; //恢复现场
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans;
return 0;
}
解题思路:
dfs过程(递归搜索树)
取自YXC讲解视频