TOJ 4267 An Easy Puz / 深搜

2024-06-15 12:18

文章标签 easy toj 4267 puz

本文主要是介绍TOJ 4267 An Easy Puz / 深搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

An Easy Puz

时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte

描述

Wddpdh find an interesting mini-game in the BBS of WHU, called “An easy PUZ”. It’s a 6 * 6 chess board and each cell has a number in the range of 0 and 3(it can be 0, 1, 2 or 3). Each time you can choose a number A(i, j) in i-th row and j-th column, then the number A(i, j) and the numbers around it (A(i-1, j), A(i+1, j),A(i, j-1),A(i, j+1), sometimes there may just be 2 or 3 numbers.) will minus 1 (3 to 2, 2 to 1, 1 to 0, 0 to 3). You can do it finite times. The goal is to make all numbers become 0. Wddpdh now come up with an extended problem about it. He will give you a number N (3 <= N <= 6) indicate the size of the board. You should tell him the minimum steps to reach the goal.

输入

The input consists of multiple test cases. For each test case, it contains a positive integer N(3 <= n <= 6). N lines follow, each line contains N columns indicating the each number in the chess board.

输出

For each test case, output minimum steps to reach the goal. If you can’t reach the goal, output -1 instead.

样例输入

样例输出

2
3

和上面一题一样暴力枚举第一行的状态下一行可以根据上一行推出来推完看最后一行是否吻合就行

求最小次数全部变成0

可以反向考虑从全部是0的矩阵变成题目输入的矩阵

深搜时第一行的含义是这个位置需要操作几次

#include <stdio.h>
#include <string.h>
const int MAX = 10;
int n;
int min;
int a[MAX][MAX];
int b[MAX][MAX];int check()
{int i,j,sum,cnt = 0;for(i = 0;i < n; i++){cnt += b[0][i];}for(i = 1; i < n; i++){for(j = 0; j < n; j++){sum = b[i-1][j];if(i > 1)sum += b[i-2][j];if(j > 0)sum += b[i-1][j-1];if(j < n - 1)sum += b[i-1][j+1];b[i][j] = (a[i-1][j] + 12 - sum ) % 4;cnt += b[i][j];}}for(j = 0; j < n; j++){sum = b[n-1][j];if(n > 1)sum += b[n-2][j];if(j > 0)sum += b[n-1][j-1];if(j < n - 1)sum += b[n-1][j+1];if((a[n-1][j] + 12 - sum) % 4)return 0x7ffffff;}return cnt;
}
void dfs(int k)
{if(k == n){int res = check();if(min > res)min = res;return;}int i;for(i = 0;i < 4; i++){b[0][k] = i;dfs(k+1);}
}
int main()
{int t,i,j;while(scanf("%d",&n)!=EOF){	for(i = 0; i < n; i++)for(j = 0; j < n; j++)scanf("%d",&a[i][j]);min = 0x7ffffff;dfs(0);if(min == 0x7ffffff)puts("-1");elseprintf("%d\n",min);}return 0;
}

这篇关于TOJ 4267 An Easy Puz / 深搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！