计算的方式来使用着色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.

下面是一些code，可以解决你的问题（我想）......它采用蛮力/回溯算法中。这里是2的输出为3种颜色，并且由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 code：

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屋！