C语言模式解码器

huangapple go评论71阅读模式
英文:

C language pattern decoder

问题

I've translated the code portion for you:

#include <stdio.h>

#define ROWS 5
#define COLS 8

int main() {
    int row_counts[] = {1, 2, 4, 3, 1};
    int col_counts[] = {1, 3, 2, 1, 0, 1, 2, 1};

    char board[ROWS][COLS];
    int i, j;

    // Initialize the board with unpainted dots
    for (i = 0; i < ROWS; i++) {
        for (j = 0; j < COLS; j++) {
            board[i][j] = '-';
        }
    }

    // Paint the dots based on row and column counts
    for (i = 0; i < ROWS; i++) {
        for (j = 0; j < row_counts[i]; j++) {
            board[i][j] = '#';
        }
    }
    
    for (j = 0; j < COLS; j++) {
        for (i = ROWS - 1; i >= ROWS - col_counts[j]; i--) {
            board[i][j] = '#';
        }
    }

    // Print the decoded pattern
    for (i = 0; i < ROWS; i++) {
        for (j = 0; j < COLS; j++) {
            printf("%c", board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

If you have any further questions or need assistance with this code, please let me know.

英文:

I am trying to develop a pattern decoder using a C language program. The pattern will be like for example:

5 8
1
2
4 
3 
1
1 3 2 1 0 1 2 1

The first row indicates the number of rows and columns. The next several rows list the count of painted squares in each row, and the final row has space-separated counts of painted squares per column.

It is a 5x8 board with painted and unpainted dots or squares. The pattern might be represented in a .txt file.
The same representation can be seen on the attached image.
The expected output is as follows, where represented by a '-' are the unpainted dots or squares and by '#' the painted ones.

Expected pattern

-#------
-##-----
####----
-----###
------#-

Program output

#-------
##------
####----
###---#-
####-###

I tried writing some code but it is not displaying or printing correctly and I have tried debugging with no success.

#include &lt;stdio.h&gt;

#define ROWS 5
#define COLS 8

int main() {
    int row_counts[] = {1, 2, 4, 3, 1};
    int col_counts[] = {1, 3, 2, 1, 0, 1, 2, 1};

    char board[ROWS][COLS];
    int i, j;

    // Initialize the board with unpainted dots
    for (i = 0; i &lt; ROWS; i++) {
        for (j = 0; j &lt; COLS; j++) {
            board[i][j] = &#39;-&#39;;
        }
    }

    // Paint the dots based on row and column counts
    for (i = 0; i &lt; ROWS; i++) {
        for (j = 0; j &lt; row_counts[i]; j++) {
            board[i][j] = &#39;#&#39;;
        }
    }
    
    for (j = 0; j &lt; COLS; j++) {
        for (i = ROWS - 1; i &gt;= ROWS - col_counts[j]; i--) {
            board[i][j] = &#39;#&#39;;
        }
    }

    // Print the decoded pattern
    for (i = 0; i &lt; ROWS; i++) {
        for (j = 0; j &lt; COLS; j++) {
            printf(&quot;%c&quot;, board[i][j]);
        }
        printf(&quot;\n&quot;);
    }

    return 0;
}

答案1

得分: 3

你可以通过以下方式将这个问题转化为最大流问题,方法如下:

  1. 存在一个单一的源顶点。
  2. 每一行都有一个顶点,从源到每一行都有一条边,容量等于行数。
  3. 每一列都有一个顶点,每一行到每一列都有一条边,容量为1。这些边对应于矩阵中的单元格。
  4. 存在一个单一的汇点顶点,每个列顶点到汇点都有一条边,容量等于列数。

现在你可以使用例如Edmonds-Karp算法从源到汇点找到最大流。然后,在你的矩阵中,如果其行->列边在流中被使用,就着色每个方块。如果你的流没有满足所有行和列的限制,那么就没有解决方案。

英文:

You can transform this problem into a max-flow problem by constructing a flow network as follows:

  1. There is a single source vertex
  2. There is a vertex for each row, and an edge from the source to each row with capacity equal to the row count.
  3. There is a vertex for each column, and an edge from each row to each column, with capacity 1. These edges correspond to the cells in your matrix.
  4. There is a single sink vertex, and an edge from each column vertex to the sink, with capacity equal to the column count.

Now you can find a maximum flow from source to sink, using, for example, the Edmonds-Karp algorithm. In your matrix, then, paint every square if its row->column edge is used in the flow. If your flow doesn't meet all the row and column limits, then there is no solution.

huangapple
  • 本文由 发表于 2023年6月15日 02:49:00
  • 转载请务必保留本文链接:https://go.coder-hub.com/76476702.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定