战车问题

问题描述

在棋盘上放置彼此不受攻击的战车。其中，战车可以攻击与之处在同一行或者同一列上的战车。在棋盘上的若干个格中设置了壁垒，战车无法穿越壁垒攻击别的战车。对于给定了设置了壁垒的n×n格棋盘，设计一个概率算法，在棋盘上放置尽可能多的彼此不受攻击的战车。

算法设计思想

每次放下一个棋子之后，先枚举其状态是横的还是竖的。然后，给它攻击范围内的所在
地的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>
#include<stdlib.h>

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 h = 1;h <= n;h++)
        for (int j = 1;j <= n;j++) //bo[i][j]如果等于1则表示可以放棋子 
            bo[h][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则表示是一个壁垒
                    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 )//如果不是壁垒，且没有其他战车会攻击到我。 
        {
            //横着放
            bo[x][y] --; //假设这地方会被攻击到。 
            bool ok = true; //判断会不会攻击到其他的战车 
            for (int i = y +1;i <= n;i++)
                if (luzhang[x][i]) //x,y的右边，如果是壁垒则攻击范围不能继续扩大了。 
                    break;
                        else
                            {
                                if (have[x][i] == true)
                                    ok = false;
                                bo[x][i]--;
                            }
            for (int r = y-1;r >= 1;r--) //这是x,y的左边 
                if (luzhang[x][r])
                    break;
                        else
                            {
                                if (have[x][r] == true)
                                    ok = false;
                                bo[x][r]--;
                            }
            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 q = y +1;q <= n;q++) //把刚才能攻击到的东西重新设置为不会被攻击到. 
                if (luzhang[x][q]) //严格来说是能攻击到这个位置的战车减少 
                    break;
                        else
                            bo[x][q]++;
            for (int p = y-1;p >= 1;p--)
                if (luzhang[x][p])
                    break;
                        else
                            bo[x][p]++;
 
            //竖着放
            bo[x][y]--; //竖着放的情况和横着放的类似 
            ok = true;
            for (int t = x+1;t <= n;t++) //同样先把竖着的目标各个位置，能攻击到的战车数递增 
                if (luzhang[t][y])
                    break;
                        else
                            {
                                if (have[t][y] == true)
                                    ok = false;
                                bo[t][y]--;
                            }
            for (int g = x-1;g >=1;g--)
                if (luzhang[g][y])
                    break;
                        else
                            {
                                bo[g][y]--;
                                if (have[g][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 d = x+1;d <= n;d++)
                if (luzhang[d][y])
                    break;
                        else
                            bo[d][y]++;
            for (int f = x-1;f >=1;f--)
                if (luzhang[f][y])
                    break;
                        else
                            bo[f][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()
{
    int t;
    scanf("%d",&t);
    for (int i = 1;i <=t;i++) //输入了t组数据 
        {
            input_data();
            tr_y(1,1);
            output_ans();
        }
	system("pause");
    return 0;
}

测试