北京市官方网站,门户网站建设意义,互联网保险现状,网站建设费摊销几年链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
题目描述
相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷#xff0c;要你根据一些信息找出雷来。
万圣节到了 #xff0c;“余”人国流行起了一种简单的扫雷游戏#xff0c;…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
题目描述
相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷要你根据一些信息找出雷来。
万圣节到了 “余”人国流行起了一种简单的扫雷游戏这个游戏规则和扫雷一样如果某个格子没有雷那么它里面的数字 表示和它8连通的格子里面雷的数目。
现在棋盘是n×2的第一列里面某些格子是雷而第二列没有雷如下图 由于第一列的雷可能有多种方案满足第二列的数的限制你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。
输入描述:
第一行为N第二行有N个数依次为第二列的格子中的数。1 ≤ N ≤ 10000
输出描述:
一个数即第一列中雷的摆放方案数。 #include iostream
#include cstdio
using namespace std;const int mxn 10010;
int n;
int f[mxn][4], g[mxn];int main() {int n;cinn;for (int i 1; i n; i)cing[i];if (g[1] 0) f[1][0] 1;else if (g[1] 1) f[1][1] f[1][2] 1;else if (g[1] 2) f[1][3] 1;for (int i 2; i n; i) {if (g[i] 0) f[i][0] f[i-1][0];if (g[i] 1) {f[i][0] f[i-1][2];f[i][1] f[i-1][0];f[i][2] f[i-1][1];}if (g[i] 2) {f[i][1] f[i-1][2];f[i][2] f[i-1][3];f[i][3] f[i-1][1];}if (g[i] 3)f[i][3] f[i-1][3];}if (g[n] 1)cout f[n-1][1] f[n-1][2]endl;if (g[n] 2) coutf[n-1][3]endl;if (g[n] 3)cout0endl;if (g[n] 0)coutf[n-1][0]endl;return 0;
}
以上的代码我搜了一下其他人写的感觉好难想啊这个是题解的链接https://www.cnblogs.com/bbqub/p/8425718.html
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
int a[10004];
int f[10004],n,i,j,ans,flag;
int hi(){for(int j2;jn;j){//从2开始判断int ta[j]-f[j-1]-f[j];//判断第i1处是否有雷if(t0 || t1) return 0;//不符合标准else f[j1]t;}if(f[n]f[n-1]!a[n]){//特批一下最后两个return 0;}return 1;
}
int main()
{scanf(%d,n);for(i1;in;i){scanf(%d,a[i]);if(a[i]3) flag1;}if(a[1]2 || a[n]2 || flag){printf(0\n);return 0;}if(a[1]2){f[1]1;f[2]1;anshi();}else if(a[1]0){f[1]0;anshi();}else if(a[1]1){f[1]1;//地雷放第一个anshi();memset(f,0,sizeof(f));f[2]1;//地雷放第二个anshi();}printf(%d,ans);
}
这个会容易理解些
a[i]第二列第i个数的值f[i]第一列的i个数是否有雷1代表有0代表无f[i-1]f[i]f[i1]a[i]--f[i1]a[i]-f[i-1]-f[i]扫雷规则
先整体来看显然对于每个a[i]的值均不能超过3因为棋盘只有一列有雷即以某点为中心最多只有3颗雷特别的第一个数和最后一个数不能超过2因为有一个被挡住了。按顺序先从第一个值进行考虑共有3种可能012。如果第一个数为0第一列第12个位置可推出没有雷通过f[i1]a[i]-f[i-1]-f[i]递推下去每个位置是否有雷为固定答案。如果第一个数为2第一列的第12个位置可推出均为雷同上式可推出每个位置是否有雷为固定答案。如果第一个数为1那么则可能有2个答案第一列的第1个位置有雷或者是第二个位置有雷当其中一个位置有雷即可推出另一个了已知两个位置用上面的递推式即可确定之后是否有雷了。
最后把其他格子的数枚举判断是否合法即可ac了。
#includebits/stdc.h
using namespace std;
#define maxn 10004
int n;
int a[maxn],b[maxn];
int ans;
void dfs(int x)
{int sum0;if(b[x-1]) sum;if(b[x]) sum;if(suma[x]-1)//下一个点必须是地雷{if(x1 n) return ; b[x1]1;//有地雷dfs(x1);b[x1]0;}if(sum!a[x]) return;if(xn){ans;return;}dfs(x1);//没有地雷。
}int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);b[1]1;dfs(1);memset(b,0,sizeof(b));dfs(1);printf(%d\n,ans);return 0;
}
上面的用dfs暴瘦一下每个点只能是有或者没有地雷按照这两个状态进行搜索即可。 每次枚举完记得判断一下是否为可行解,进行剪枝。 注意一下第一个点要分类讨论放不放地雷。
突然发现想复杂了其实看了大佬的代码是这样的
#includeiostream
using namespace std;
int n,a[10005],f[10005],ans0;
int main()
{cinn;for(int i1;in;i) cina[i];for(int i0;ia[1];i){f[1]i;for(int j2;jn1;j)f[j]a[j-1]-f[j-1]-f[j-2];if(f[n1]0) ans;}coutans;
}
#includeiostream
using namespace std;
const int N1e510;
int ans;
int a[N];
int n;
void dfs(int x,int lst,int now){if(x n1 now0 ) {ans;return;}if(now lst a[x]) return ;dfs(x1,now,a[x]-lst-now);
}
int main(){cinn;for(int i1;in;i) cina[i];dfs(1,0,1);dfs(1,0,0);coutans\n;return 0;
}
#includebits/stdc.h
using namespace std;
const int N100010;
int n,a[N],f[N],ans;
bool check(){for(int i2;in;i){f[i]a[i-1]-f[i-1]-f[i-2];if(f[i]0||f[i]1) return 0;}return a[n]f[n]f[n-1];
}
int main()
{cinn;for(int i1;in;i) cina[i];f[1]1;if(check()) ans;f[1]0;if(check()) ans;coutans;
}
#includebits/stdc.husing namespace std;int n,a[2][10005];
int i;bool b(bool k){a[1][1]k;for(i1;in;i){if(a[1][i]a[1][i-1]a[0][i]){return 0;}a[1][i1]a[0][i]-a[1][i-1]-a[1][i];}return !a[1][n1];
}int main()
{int i;scanf(%d,n);for(i1;in;i){scanf(%d,a[0][i]);}printf(%d\n,b(0)b(1));return 0;
}
