行列棋盘 - BFS思想

0.题目

先放一下这一题的题目：

题目描述

您将获得一个n行m列的棋盘。棋盘的每个格子都包含一个数字 0 或 1。在一次移动中，我们可以选择棋盘的某一行，并循环地将其值向左移动一个单元格，或向右移动一个单元格。

将表格行循环向右移动一个单元格意味着将每个单元格（最后一个单元格除外）的值移动到右侧相邻单元格，并将最后一个单元格的值移动到第一个单元格。行向左的移动类似，但在另一个方向上执行。例如，如果我们循环地将一行"00110"向右移动一个单元格，我们得到一行"00011"，但是如果我们向左移动一行"00110"一个单元格，我们得到一行"01100"。

确定使某列仅由数字 1 组成所需的最小移动次数。

输入

第一行包含两个以空格分隔的整数：n（1 ≤ n ≤ 100），m（1 ≤ n ≤ 10000）

然后n行，每行包括m个字符"0"或"1"

输出

输出单个数字：在表格的某些列中仅获得数字 1 所需的最小移动次数。如果无法做到这一点，请输出 -1。

样例输入

3 6
101010
000100
100000

样例输出

3

1.基本思路

先利用bfs计算每一行的0，把那个位置的0变成让那个位置变为1的最小步数，然后一列一列加起来，取最小值即可。

2.AC代码

#include
#include
int main() {
    int n , m;
    scanf("%d",&n);
    scanf("%d",&m);
    int p[101][10001] = {0};
    for (int i = 0; i < n; i++)
    {
        char* input = (char*)calloc(sizeof(char), m + 1);
        scanf("%s", input);
        for (int j = 0; j < m; j++)
        {
            if (input[j] == '0') {
                int offset = 1;
                int left = 0, right = 0;
                while (left==0||right==0) {
                    if (left == 0) {
                        if (j-offset<0) {
                            if (offset>m/2+1) {
                                left = -1;
                            }
                            else {
                                if (p[i][m - j + offset] != 0) {
                                    left = p[i][m - j + offset] + offset;
                                }
                                else if (input[ m - j + offset] == '1') {
                                    right = 1 + offset;
                                }
                            }
                        }
                        else if(p[i][j - offset]!=0) {
                            left = p[i][j - offset] + offset;
                        }
                        else if(input[j-offset] == '1') {
                            right = 1 + offset;
                        }
                    }
                    if(right==0) {
                        if (j + offset >= m) {
                            if (offset > m / 2 + 1) {
                                right = -1;
                            }
                            else {
                                if (p[i][j + offset - m] != 0) {
                                    right = p[i][j + offset - m] + offset;
                                }
                                else if (input[j + offset - m] == '1') {
                                    right = 1 + offset;
                                }
                            }
                        }
                        else if (p[i][j + offset] != 0) {
                            right = p[i][j + offset] + offset;
                        }
                        else if (input[j+offset] == '1') {
                            right = 1 + offset;
                        }
                    }
                    offset++;
                }
                if (left==-1||right==-1) {
                    if (left == -1 && right == -1) {
                        printf("-1");
                        return 0;
                    }
                    else if (left == -1) {
                        p[i][j] = right;
                    }
                    else {
                        p[i][j] = left;
                    }
                }
                else if (left