本文介绍了编程逻辑/伪代码的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我需要为我的课做一些伪代码,但我对如何解决这个问题感到困惑:

I need to make some pseudocode for my class and I am stumped on how to do this question:

有一个NxN网格(1

There is an NxN grid (1 < N < 1300). You have to place exactly 2 items in every 2x2 subgrid (Assume that there is a solution for every case). Print every solution.

输入示例:3

输出示例:

111
000
111

000
111
000

101
010
101


010
101
010

等...(其中0是一个空白空间,并占用了1)

etc...(where 0 is an empty space and 1 is taken)

奖金:如果对网格中的每个正方形都进行了加权,请说明如何找到最佳解决方案.

Bonus: If every square in the grid was weighted, explain how you can find the best solution.

推荐答案

一种生成某些解决方案的简单方法是任意选择第一行,然后通过减去前一行减去每一行.我们也可以使用列来做到这一点.

A simple method to generate some solutions is to pick a first row arbitrarily and then fill out each subsequent row by taking one minus the previous row. We can also do this with columns.

事实证明,每个有效矩阵都是由这两个变体之一生成的(请注意,两个完美的棋盘格都是由两者生成的).原因是,如果第一行具有相邻的零或相邻的零,则将强制其下的条目,这将迫使该行的其余部分减一,再减去前一行,并依次强制其余的行.同上的列.如果第一行和第一列都没有重复,那么我们有两个棋盘格之一.

It turns out that every valid matrix is generated by one of these two variants (note that the two perfect checkerboards are generated by both). The reason is that if the first row has adjacent zeros or adjacent ones, then the entries below it are forced, these force the rest of the row to be one minus the previous row, and in turn the rest of the rows are forced. Ditto columns. If neither the first row nor the first column has a duplicate, then we have one of the two checkerboards.

最大化并不难.对于交替的行,请为每列确定偶数行还是奇数行是否更有价值.对于交替列,请为每行确定偶数列还是奇数列是否更有价值.充分利用这两种解决方案中的优势.

Maximizing isn't too hard. For alternating rows, decide for each column whether the even rows or the odd rows are more valuable. For alternating columns, decide for each row whether the even columns or the odd columns are more valuable. Take the best of these two solutions.

这篇关于编程逻辑/伪代码的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-15 21:51
查看更多