2

4

.X..

....

XX..

....

3

...

...

...

    

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\n",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;

}