当前位置: 代码迷 >> 综合 >> ZOJ3861 Valid Pattern Lock(DFS||打表+枚举)
  详细解决方案

ZOJ3861 Valid Pattern Lock(DFS||打表+枚举)

热度:31   发布时间:2024-01-16 13:52:10.0

题意:

手机九宫格锁,共9个数,然后给出规定,只能用给定的n个数做密码,求不同的锁屏方法有几种
对于一个点可以走向其他相邻8个方向,对于中间有相互隔开的情况,例如1到3,如果2已经访问过,那么方案是可行的,输出所有锁屏方案路径

要点:

可以DFS或直接排列判断,排列的话主要的难点在于判断是否合法,因为数据较小,直接打表出要考虑的几种情况,并用一个vis数组对每一个排列从头到尾进行是否走过的记录。我反正是想不出来,看了别人的代码感觉还算简单,还是太弱鸡了。


打表+枚举:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int mp[15][15],a[15];
int vis[15];
int result[400000][15];
int n;void init()	//打表,不能通过的顺序
{mp[1][3] = 2; mp[3][1] = 2;mp[1][7] = 4; mp[7][1] = 4;mp[1][9] = 5; mp[9][1] = 5;mp[2][8] = 5; mp[8][2] = 5;mp[3][7] = 5; mp[7][3] = 5;mp[3][9] = 6; mp[9][3] = 6;mp[4][6] = 5; mp[6][4] = 5;mp[7][9] = 8; mp[9][7] = 8;
}bool check()		//按照当前排列顺序走能否成功
{vis[a[0]] = 1;	//记录是否走过for (int i = 1; i < n; i++){int v = mp[a[i - 1]][a[i]];//当前连续的两个中间的值,看是否需要跳过if (!(!v || vis[v]) && (!vis[a[i]]))//成功的条件:不用考虑跳过或要跳过的已经走过并且当前还没走过return false;		//整个取反输出失败vis[a[i]] = 1;			//当前的已经走过}return true;
}int main()
{int t,i,j;scanf("%d", &t);while (t--){memset(mp, 0, sizeof(mp));init();scanf("%d", &n);for (i = 0; i < n; i++)scanf("%d", &a[i]);sort(a, a + n);			//因为要按字典序输出,所以先排序int num = 0;do{memset(vis, 0, sizeof(vis));if (check()){num++;memcpy(result[num], a, sizeof(a));}} while (next_permutation(a, a + n));//直接下一个排列printf("%d\n", num);for (i = 1; i <= num; i++){for (j = 0; j < n - 1; j++)printf("%d ", result[i][j]);printf("%d\n", result[i][n-1]);}}return 0;
}

DFS:

对于每一个点都可以往剩下的8个点走。重点就是不断两个两个比较,然后传递第二个作为下一次的第一个

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int vis[300],a[11],mp[11][11];
int ans[400000][11],f[11];
int n,len;void init()
{mp[1][3] = 2; mp[3][1] = 2;mp[1][7] = 4; mp[7][1] = 4;mp[1][9] = 5; mp[9][1] = 5;mp[2][8] = 5; mp[8][2] = 5;mp[3][7] = 5; mp[7][3] = 5;mp[3][9] = 6; mp[9][3] = 6;mp[4][6] = 5; mp[6][4] = 5;mp[7][9] = 8; mp[9][7] = 8;
}
void print()
{for (int i = 0; i < n; i++){ans[len][i] = f[i];}len++;
}
void dfs(int cur,int x)
{if (x == n){print();return;}for (int i = 0; i <n; i++){if (vis[a[i]] == 0 && (mp[a[i]][cur] == 0 || vis[mp[a[i]][cur]] == 1))//判断方式跟枚举一样{vis[a[i]] = 1;f[x] = a[i];dfs(a[i], x + 1);//a[i]作为cur传递,相当于两个两个比较vis[a[i]] = 0;//有多种,递归不成功改回来}}
}int main()
{int t;scanf("%d", &t);memset(mp, 0, sizeof(mp));init();while (t--){len = 0;memset(vis, 0, sizeof(vis));scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d", &a[i]);sort(a, a + n);			//字典序排序dfs(0,0);			//第一次传递cur为0时相当于还没开始比较两个,必定成功printf("%d\n", len);for (int i = 0; i < len; i++){for (int j = 0; j < n-1; j++)printf("%d ", ans[i][j]);printf("%d\n",ans[i][n-1]);//输出有点严格,不能多空格}}return 0;
}




  相关解决方案