AOJ 845.黑白棋|OhYee 博客

这是一篇最后编辑于 8 年前的文章，其内容可能与目前实际情况差异较大，请注意甄别

题目

{% raw %}

{% endraw %} 小红和小绿在玩一个摆棋子游戏. 小红在桌上摆了12个棋子, 棋子分黑和白两个颜色. 小绿给出a, b两个正整数使得a和b的积为12, 然后依次取小红摆好的棋子中的前b个放到一列, 然后再取剩下来的棋子中的前b个放到第二列, ..., 直到摆成一个a*b的棋子矩阵. 当矩阵中存在某一列或某些列全部为黑棋子时, 小绿成功完成这轮游戏, 否则失败.

现在小红已经把棋子摆好了, 请帮助小绿算出所有能让小绿成功完成游戏的a和b的选择方案.

{% raw %}

{% endraw %}

第一行: 给出数据组数, t(1≤t≤100);
接下来t行: 每行12个字符, 表示小红摆好的棋子序列, 字符'X'表示黑棋, 'O'表示白棋.

{% raw %}

{% endraw %}

一共t行, 一行对应一组输入数据的所有方案;
对于一组数据, 先输出小绿可以成功完成游戏的方案数n, 接下来给出以'axb'的格式给出这n个方案, a值小的方案先输出. 方案之间用一个空格隔开.

{% raw %}

{% endraw %}

4
OXXXOXOOXOOX
OXOXOXOXOXOX
XXXXXXXXXXXX
OOOOOOOOOOOO

{% raw %}

{% endraw %}

3 1x12 2x6 4x3
4 1x12 2x6 3x4 6x2
6 1x12 2x6 3x4 4x3 6x2 12x1
0

{% raw %}

{% endraw %}

题解

模拟跑一下就行,按照指定的要求分成制定的行列,最后看有没有一行全是黑棋(题目应该是表达错了,不过可以根据样例自己推出来)

代码

```cpp 黑白棋 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include

//*/ #include #include #include using namespace std;

const int ans[][2] = {{1,12},{2,6},{3,4},{4,3},{6,2},{12,1}};
bool answ[6];
bool a[12];
bool Map[12][12];

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int T;
cin >> T;
while(T--){
    for(int i=0;i<12;i++){
        char t;
        cin >> t;
        a[i] = t=='X';
    }
    memset(answ,false,sizeof(answ));

    for(int i=0;i<6;i++){
        int pos=0;
        for(int x=0;x<ans[i][0];x++){
            for(int y=0;y<ans[i][1];y++){
                Map[x][y] = a[pos++];
            }
        }

        bool OK = true;
        for(int y=0;y<ans[i][1];y++){
            OK = true;
            for(int x=0;x<ans[i][0];x++){
                if(!Map[x][y]){
                    OK = false;
                    break;
                }
            }
            if(OK)
                break;
        }
        if(OK)
            answ[i] = true;
    }

    int cnt=0;
    for(int i=0;i<6;i++)
        cnt+=(int)answ[i];
    cout << cnt;
    for(int i=0;i<6;i++)
        if(answ[i])
            cout << " " << ans[i][0] << "x"<< ans[i][1];
    cout << endl;

}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>

推荐订阅源

OhYee 博客

题目

题解

代码