计算使用K颜色为N * M网格着色的方法数 [英] Calculate the number of ways to color an N * M grid using K colors
问题描述
我想问你如何计算使用K颜色来着色N * M网格的方法的数量。网格中的相邻正方形应该有不同的颜色。如果它们共享边缘,则认为相邻。有没有一个快速算法来做到这一点?
I wanna ask you how to calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge. Is there a fast algorithm to do that?
推荐答案
注意:我假设我们没有使用每种颜色。
NOTE: I am assuming that we do not have use every color. If we do, additional checks can easily be applied.
这里有一些代码可以解决你的问题(我想)...它使用强力/回溯算法。这里是3种颜色的输出,2×3的网格。它打印它找到的每个组合。对于此输入,答案是54。
Here is some code that can solve your problem (I think)... It uses a brute force / backtracking algo. Here is the output for 3 colors, and 2 by 3 grid. It prints every combination that it found. For this input, the answer is 54.
Enter number of colors: 3
Enter number of rows: 2
Enter number of columns: 3
121
212
121
213
123
212
121
232
123
231
123
232
131
212
131
213
132
213
121
312
121
313
123
312
131
312
131
313
132
313
131
323
132
321
132
323
212
121
212
123
213
121
212
131
213
131
213
132
231
123
232
121
232
123
212
321
212
323
213
321
231
312
231
313
232
313
231
323
232
321
232
323
312
121
312
123
313
121
312
131
313
131
313
132
321
132
323
131
323
132
312
231
313
231
313
232
321
212
321
213
323
212
321
232
323
231
323
232
There are 54 different combinations of 3 colors.
这里是一个Java代码:
Here is a Java code:
import java.util.*;
public class ColorChoices
{
int[][] grid;
int numberOfColors;
int numberOfRows;
int numberOfColumns;
int numberOfCombinations;
public static void main(String[] args)
{
ColorChoices solution = new ColorChoices();
solution.begin();
}
void begin()
{
numberOfCombinations = 0;
Scanner consoleInput = new Scanner(System.in);
System.out.print("Enter number of colors: ");
numberOfColors = consoleInput.nextInt();
System.out.print("Enter number of rows: ");
numberOfRows = consoleInput.nextInt();
System.out.print("Enter number of columns: ");
numberOfColumns = consoleInput.nextInt();
grid = new int[numberOfRows][numberOfColumns];
solve(0, 0);
System.out.println("There are " + numberOfCombinations + " different combinations of " + numberOfColors + " colors.");
}
void solve(int r, int c)
{
for(int i = 1; i <= numberOfColors; i++)
{
if(valid(r, c, i))
{
grid[r][c] = i;
if(r == numberOfRows - 1 && c == numberOfColumns - 1)
{
printBoard();
numberOfCombinations++;
}
else if(r == numberOfRows - 1) solve(0, c + 1);
else solve(r + 1, c);
}
}
grid[r][c] = 0;
}
boolean valid(int r, int c, int n)
{
return(leftOK(r, c, n) && rightOK(r, c, n) && topOK(r, c, n) && bottomOK(r, c, n));
}
boolean leftOK(int r, int c, int n)
{
if(c == 0) return true;
if(grid[r][c - 1] != n) return true;
return false;
}
boolean rightOK(int r, int c, int n)
{
if(c == numberOfColumns - 1) return true;
if(grid[r][c + 1] != n) return true;
return false;
}
boolean topOK(int r, int c, int n)
{
if(r == 0) return true;
if(grid[r - 1][c] != n) return true;
return false;
}
boolean bottomOK(int r, int c, int n)
{
if(r == numberOfRows - 1) return true;
if(grid[r + 1][c] != n) return true;
return false;
}
void printBoard()
{
for(int i = 0; i < numberOfRows; i++)
{
for(int j = 0; j < numberOfColumns; j++)
{
System.out.print(grid[i][j]);
}
System.out.println();
}
System.out.println();
}
}
这篇关于计算使用K颜色为N * M网格着色的方法数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!