这是19年度的打题记录,感觉学会了很多奇奇怪怪的算法哈哈哈哈,还是深搜让我印象深刻
这题迷宫硬是在机房磕了2个小时,当时真的是憨憨
一个DFS写了15分钟……
int dfs(int pos, int sum) //pos是点 0,1,2
{
// 3,4,5
int r = pos / n; //行 1/3=0 3/3=1
int c = pos % n; //列 1%3=1 3%3=0
if (pos == n * n) //如果所有的点都走了一遍（边界条件）
{
if (sum > max)
max = sum;
return max;
}
if (s[r][c] == ‘.’)
{
if (check(r, c)) //检查该点建炮台是否冲突
{
s[r][c] = ‘P’; //标志该点建了炮台
dfs(pos + 1, sum + 1);//遍历该点的所有可能性
s[r][c] = ‘.’; //恢复到原来的样子
}
}
dfs(pos + 1, sum); //如果不符合条件
}
要不是判定没思路也不至于skr~
int check(int r, int c)
{
for (int i = c; s[r][i] != ‘X’ && i >= 0 ; i–)
{
if (s[r][i] == ‘P’)//左
{
return 0;
}
}
for (int i = r; s[i][c] != ‘X’ && i >= 0; i–)
{
if (s[i][c] == ‘P’)//上
{
return 0;
}
}
return 1;
}
就这样草草结束?不可能的
对,还有一行自我批斗哈哈哈,我真是个傻憨憨