Time Limit: 1 second
Memory Limit: 50 MB
【问题描述】
按照国际象棋的规则，车可以攻击与之处在同一行或同一列上的棋子。指南车是有方向的车。横向指南车可以攻击与之处在同一行上的棋子。纵向指南车可以攻击与之处在同一列上的棋子。在一个n×n的棋盘上，有些格子被障碍物占据。现在在棋盘上空白的格子里放置一些方向未定的指南车。为了避免不同指南车之间的冲突，对于任意一辆指南车，在其攻击范围之内，不能放置另外一辆指南车。指南车的方向将在放置的时候，由你来决定。
图1是一个4*4棋盘上有3个格子被障碍物占据的空白棋盘，没有放置指南车。
图2，图3是合法放置指南车的局面。
图4，图5是非法放置指南车的局面，指南车会相互攻击。
编程任务:
求在给定局面下，最多可以放置“指南车”的个数。
【输入】
第一行一个整数T (1 ≤ T ≤ 1,000)，表示测试数据的组数。接下来有T组测试数据，每组测试数据的第一行是一个整数n（1 ≤ n ≤ 5），表示棋盘的大小为n*n，接下来的n行n列，接下来表示棋盘的局面。其中'X'表示有障碍物，'.'表示空白格子。
【输出】
对于每组测试数据，输出一行一个整数表示最多可以放置“指南车”的个数。
【输入样例】
2 4 .X.. .... XX.. .... 3 ... ... ...
【输出样例1】
7 4
【题解】
这道搜索题，主要考察对判重，回溯方法的掌握。
只有5*5，所以直接爆搜就可以了。
每次放下一个棋子之后，先枚举其状态是横的还是竖的。然后，给它攻击范围内的所在
地的bo[x][y]--,不能直接置为false,因为bo[x][y]代表的是x,y这个坐标能放棋子的程度，假想一下，如果一个位置，你两个已经放下的棋子都能攻击得到，如果其中一个棋子要开始回溯(拿走了)，你不能单纯的就置那个两个棋子都能攻击到的点为false，而应该用递减来表示少了一个棋子能攻击到他。然后回溯的时候，把横的攻击范围或竖的攻击范围bo[x][y]++,这样回溯比较方便，且不会出错。然后在设置攻击范围的时候，如果遇到了障碍物，则停止继续设置，或者遇到了have[x][y]
== true(这个位置有另外一个棋子),则这个状态是不合理的。之后have[x0][y0]=true,即设置这个位置放了一个棋子。
【题解】
#include <cstdio>
#include <cstring>
int n;
char* m[7];
bool luzhang[10][10],have[10][10]; //luzhang[][]判断是否为路障，have[][]是否有忧忧被放置
int bo[10][10],num = 0,max_n = 0; //bo[][]表示某个位置被忧忧攻击的程度。(为1则表明为0个忧忧，越小表明被能被越多的忧忧攻击到)
void input_data()
{
max_n = 0;
//给bo数组赋值为1不能直接用memset.
memset(have,false,sizeof(have));
memset(luzhang,false,sizeof(luzhang));
scanf("%d",&n);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++) //bo[i][j]如果等于1则表示可以放棋子
bo[i][j] = 1;
getchar(); //前面输入的是整形，后面输入字符串，且不是用cin则一定要加getchar
for (int i = 1;i <= n;i++)
{
m[i] = new char [10];
scanf("%s",m[i]); //输入一个字符串
for (int j = 1;j <= n;j++)
if (m[i][j-1] == 'X') //如果是X则表示是一个joy
luzhang[i][j] = true;
}
}
void tr_y(int x,int y)
{
if (num > max_n) //如果能够更新解，则更新
max_n = num;
if (x > n) return;
if (y > n) return; //这是越界的情况
//可以放的情况
if (!luzhang[x][y] && bo[x][y] == 1 )//如果不是joy，且没有其他忧忧会攻击到我。
{
//横着放
bo[x][y] --; //假设这地方会被攻击到。
bool ok = true; //判断会不会攻击到其他的忧忧
for (int i = y +1;i <= n;i++)
if (luzhang[x][i]) //x,y的右边，如果是joy则攻击范围不能继续扩大了。
break;
else
{
if (have[x][i] == true)
ok = false;
bo[x][i]--;
}
for (int i = y-1;i >= 1;i--) //这是x,y的左边
if (luzhang[x][i])
break;
else
{
if (have[x][i] == true)
ok = false;
bo[x][i]--;
}
num++; //先假设能多放一个
if (ok) //如果不会攻击到其他忧忧
{
have[x][y] = true; //放置一个忧忧到这个位置
if (y == n) //根据当前的坐标判断下一个尝试的目标是什么
tr_y(x+1,1);
else
tr_y(x,y+1);
have[x][y] = false;//回溯
}
num--;//回溯
bo[x][y]++;//回溯
for (int i = y +1;i <= n;i++) //把刚才能攻击到的东西重新设置为不会被攻击到.
if (luzhang[x][i]) //严格来说是能攻击到这个位置的忧忧减少
break;
else
bo[x][i]++;
for (int i = y-1;i >= 1;i--)
if (luzhang[x][i])
break;
else
bo[x][i]++;
//竖着放
bo[x][y]--; //竖着放的情况和横着放的类似
ok = true;
for (int i = x+1;i <= n;i++) //同样先把竖着的目标各个位置，能攻击到的忧忧数递增
if (luzhang[i][y])
break;
else
{
if (have[i][y] == true)
ok = false;
bo[i][y]--;
}
for (int i = x-1;i >=1;i--)
if (luzhang[i][y])
break;
else
{
bo[i][y]--;
if (have[i][y] == true)
ok = false;
}
num++;
if (ok)
{
have[x][y] = true;
if (y == n)
tr_y(x+1,1);
else
tr_y(x,y+1);
have[x][y] = false;
}
num--; //回溯
for (int i = x+1;i <= n;i++)
if (luzhang[i][y])
break;
else
bo[i][y]++;
for (int i = x-1;i >=1;i--)
if (luzhang[i][y])
break;
else
bo[i][y]++;
bo[x][y]++;
}
//不放的情况 则直接找下一个搜索的目标
if (y == n)
tr_y(x+1,1);
else
tr_y(x,y+1);
}
void output_ans()
{
printf("%d
",max_n);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
int t;
scanf("%d",&t);
for (int i = 1;i <=t;i++) //输入了t组数据
{
input_data();
tr_y(1,1);
output_ans();
}
return 0;
}