我有网格N×M,其中每个单元格都用一种颜色着色.
当玩家点击颜色α的网格的任何单元格时,网格的顶部左上角的单元格β,接收颜色α,但不仅如此:所有这些通过连接到源的单元格仅使用颜色α或β的路径也接收颜色α.
单元格之间的连接应仅在水平和垂直方向上考虑以形成路径.例如,当玩家点击左侧图中突出显示的单元格时,网格会接收图形向右的着色.游戏的目标是使网格单色.
输入说明
The first line of the input consists of 2 integers N and M (1 ≤ N ≤ 4,1 ≤ M ≤ 5),which represent respectively the number of lines and the number of columns of the grid. The N lines following describe the initial configuration of the grid,representing each colour by an integer between 0 and 9. The input does not consist of any other line.
输出说明
Print a line containing a single integer that represents the minimum number of clicks that the player must do in order to make the grid monochromatic.
输入样品
1:
4 5 01234 34567 67890 90123
2:
4 5 01234 12345 23456 34567
3:
4 5 00162 30295 45033 01837
输出样本
1:
12
2:
7
3:
10
我试图找到一个解决方案与回溯(由于时间限制8秒和小尺寸的网格).但是超出了时间限制.有些人只是在0秒钟内完成.
还有一些其他算法来解决这个问题?
#include <stdio.h>
#include <string.h>
#define MAX 5
#define INF 999999999
typedef int signed_integer;
signed_integer n,m,mink;
bool vst[MAX][MAX];
signed_integer flood_path[4][2] = {
{-1,0},{1,{0,1},-1}
};
//flood and paint all possible cells... the root is (i,j)
signed_integer flood_and_paint(signed_integer cur_grid[MAX][MAX],signed_integer i,signed_integer j,signed_integer beta,signed_integer alpha,signed_integer colors[]){
//invalid cell
if (vst[i][j] || i < 0 || i >= n || j < 0 || j >= m)
return 0;
//mark existent colors
colors[cur_grid[i][j]] = 1;
//only alpha and beta colors counts
if (cur_grid[i][j] != beta && cur_grid[i][j] != alpha)
return 0;
//mark (i,j) as visited and change its color
vst[i][j] = true;
cur_grid[i][j] = alpha;
//floodit !
signed_integer ret = 1;
for (signed_integer k = 0; k < 4; k++)
ret += flood_and_paint(cur_grid,i + flood_path[k][0],j + flood_path[k][1],beta,alpha,colors);
//how many cells change
return ret;
}
void backtrack(signed_integer cur_grid[MAX][MAX],signed_integer k,signed_integer _cont,signed_integer alpha) {
//bigger number of clicks for this solution ? ... getting back
if(k >= mink)
return;
signed_integer colors[10];
memset(vst,false,sizeof(vst));
memset(colors,sizeof(colors));
signed_integer beta = cur_grid[0][0];
signed_integer cont = flood_and_paint(cur_grid,colors);
//there are alpha colors to change and no beta colors to change
colors[alpha] = 1;
colors[beta] = 0;
//all squares on same color
if (cont == n * m) {
mink = k;
return;
}
//this solution is equals to another ? ... getting back
if (cont == _cont)
return;
++k;//new click
//copy this matrix and backtrack
signed_integer copy[MAX][MAX];
for (signed_integer c = 0; c < 10; ++c){
if (colors[c] && c != cur_grid[0][0]) {
memcpy(copy,cur_grid,n*m*sizeof(signed_integer));
backtrack(copy,k,cont,c);
}
}
}
void cleanBuffer(){
while (getchar() != 'n');
}
int main(void) {
signed_integer grid[MAX][MAX];
scanf("%d %d",&n,&m);
for (signed_integer i = 0; i < n; ++i) {
cleanBuffer();
for (signed_integer j = 0; j < m; ++j){
grid[i][j] = getchar() - '0';
}
}
mink = INF;
backtrack(grid,grid[0][0]);
printf("%dn",mink);
return 0;
}
解决方法
高水平的改善
请注意,单元格是其原始颜色或最后选定的颜色.
这意味着我们可以用20位表示电路板的当前状态(4 * 5单元中的每个单元的标记是否包含原始颜色)以及范围为0到9的数字,给出最后选择的颜色.
这导致最多可以探索1000万个州.回溯功能可以避免如果达到已经访问的状态,则必须进行递归.我希望这个更改能够使您的解决方案更快.
水平提高
通过20bit掩码表示状态,最后一种颜色也使得状态更快更新,因为只需要更改2个数字,而不是全板的memcpy.
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|