草庐IT

牛客之数独合理吗？

不会敲代码的破茧 2023-04-03 原文

文章目录


链接：https://ac.nowcoder.com/acm/contest/19306/1025
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

众所周知，数独是一款简单上手（划掉）且极易打发时间的游戏，
fishfloss喜欢玩数独，虽然自己很菜。
数独的具体规则是这样的：
需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，
并满足每一行、每一列、每一宫（3x3）内的数字均含1-9并不重复

例如 ：

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
就是一个合法的数独的解
而
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 4
则不是
那么下面给出数独盘面，来判断一下它是否是数独的合法解吧

输入描述:

输入共9行，每行9个数，代表数独盘面

输出描述:

一行，如果输入是数独的合法解，则输出YES
反之输出NO

示例1

输入
复制
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
输出
复制
YES

示例2

输入
复制
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 4
输出
复制
NO

说明

对于宫9，行9及列9，显然有重复的4，故不满足合法解

用于学习记录，如果大佬有更好的解法，欢迎大佬指教

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<math.h>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long LL;
int a[15][15],f[10];
int check(int i,int j)
{
memset(f,0,sizeof(f));//初始化f

 for(int k1=(i/3)*3+1;k1<=(i/3)*3+3;k1++)//转化求每一个三宫
{
 for(int k2=(j/3)*3+1;k2<=(j/3)*3+3;k2++)
 {
   if(!f[a[k1][k2]])
   {
    f[a[k1][k2]]=1;
   }
   else
   {
    return 1;
   }
 }
}
  return 0;
}
int main()
{
for(int i=1;i<=9;i++)
{
 for(int j=1;j<=9;j++)
 {
  cin>>a[i][j];
 }
}
int flag=0;
//行检查
for(int i=1;i<=9;i++)
{
memset(f,0,sizeof(f));
 for(int j=1;j<=9;j++)
 {
  if(!f[a[i][j]])
  {
   f[a[i][j]]=1; 
  }
  else
  {flag=1;
   break;
  }
 }
 if(flag)
 break;
}
if(!flag){//列检查
for(int i=1;i<=9;i++){
 memset(f,0,sizeof(f));
 for(int j=1;j<=9;j++)
 {
  if(!f[a[j][i]])
  {
   f[a[j][i]]=1;
  }
  else
  {
      flag=1;
   break;
  }
 }
 if(flag)
 break;
}
}
 if(!flag)//三宫检查
 {
  for(int i=1;i<=9;i+=3)
  {
  for(int j=1;j<=9;j+=3)
  {
  flag=check(i,j);
  if(flag)
  {
  break;
  }
  }
  if(flag)
  {
  break;
  }
  }
 }
if(!flag)
 cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}

欢迎大佬指点一二

牛客之数spanclasstokenc++$算法$图论

有关牛客之数独合理吗？的更多相关文章

  1. 牛客网专项练习30天Pytnon篇第02天 - 2

    1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析：    在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1:    print(k)k=k/2A.1000 B.10C.11D.9解析：    按照题意每次循环K/2，直到K值小于等

  2. ruby - 这是 &&= 在 Ruby 中的合理用法吗？ - 2

    在SOquestion2068165一个答案提出了使用这样的东西的想法:params[:task][:completed_at]&&=Time.parse(params[:task][:completed_at])作为DRYer的说法params[:task][:completed_at]=Time.parse(params[:task][:completed_at])ifparams[:task][:completed_at]paramsHash将来自(Rails/ActionView)表单。这是众所周知的||=习语的一种推论，如果LHS不是nil/false则设置值。像这样使用&&

  3. ＜Java＞逻辑控制，方法详解，重载，牛客习题，IDEA调试方法... - 2

    目录一.逻辑控制+方法1.java输入2.循环输入3.switch4.循环结构 5.三种输出6.java生成随机数7.java方法二.习题+方法21.返回二进制中1的个数2.获取一个二进制序列中的偶数位和奇数位，分别输出二进制序列3.JAVA比较字符串是否相同4.牛客网ACM书写格式5.方法的重载一.逻辑控制+方法1.java输入注意大小写！下面代码会出现什么问题？？2.循环输入Ctrl+D结束循环输入3.switch面试问题：不能做switch()参数的类型有哪些？longfloatdoubleboolean(其他的都可以)4.循环结构 continue该程序运行的结果是什么？？5.三种输出

  4. 牛客竞赛每日俩题 - 动态规划3 - 2

    目录类01背包问题，选or不选变种走方格类01背包问题，选or不选不同的子序列_牛客题霸_牛客网问题翻译：        S有多少个不同的子串与T相同        S[1:m]中的子串与T[1:n]相同的个数        由S的前m个字符组成的子串与T的前n个字符相同的个数状态：        子状态：由S的前1,2,...,m个字符组成的子串与T的前1,2,...,n个字符相同的个数        F(i,j):S[1:i]中的子串与T[1:j]相同的个数状态递推：        在F(i,j)处需要考虑S[i]=T[j]和S[i]!=T[j]两种情况        当S[i]=T[j]

  5. ruby - Ruby 中的 `eval` 何时合理？ - 2

    "Is'eval'supposedtobenasty?"启发了这个:大多数人都认为eval不好，并且在大多数情况下有更优雅/更安全的替代品。所以我想问:如果eval经常被滥用，是否真的需要它作为一种语言特性？是不是弊大于利？就个人而言，我发现它唯一有用的地方是插入配置文件中提供的字符串。编辑:这个问题的目的是在eval是唯一或最佳解决方案时获得尽可能多的真实案例。所以请不要进入“语言是否应该限制程序员的创造力”的方向。Edit2:当我说eval时，我当然指的是eval字符串，而不是将ruby​​block传递给instance_eval或class_eval.

  6. ruby - 将整个文本文件作为单个字符串读取的合理方法是什么？ - 2

    我相信这很容易；我无法立即从Google找到答案。我知道我可以做到这一点(对吧？):text=""File.open(path).each_linedo|line|text+=lineend#Dosomethingwithtext但这似乎有点过分，不是吗？或者这是人们在Ruby中的做法吗？ 最佳答案 IO.read()正是您要找的。File是IO的子类,所以你也可以使用:text=File.read(path)没有比这更直观的了。 关于ruby-将整个文本文件作为单个字符串读取的合理方法

  7. javascript - 合理数量的同时异步 ajax 请求 - 2

    我想知道关于通常允许多少同时异步ajax请求的共识是什么。我问的原因是我正在开发个人网络应用程序。在大多数情况下，我将我的请求减少到一个。但是，在某些情况下，我最多同时发送4个请求。这会造成一点延迟，因为浏览器一次只能处理2个。目前，就可用性而言，延迟不是问题。如果有的话，我还需要一段时间才能担心可伸缩性。但我正在努力遵守最佳实践，尽可能合理。你都有些什么想法呢？4个请求是一个合理的数字吗？ 最佳答案 我很确定浏览器无论如何都会限制您可以拥有的连接数。如果您有Firefox，请输入about:config并查找network.htt

  8. javascript - 使用 John Resig 的 Processing.js 是否合理？ - 2

    我正在考虑制作一个使用相当密集的JavaScript/canvas的网站，我一直在查看Processing.js在我看来，这将使操作Canvas变得更加容易。有谁知道我不应该使用Processing.js的原因吗？我知道旧版浏览器将无法使用它，但现在没关系。 最佳答案 如前所述，Processing.js(包括IE8beta)不支持IE。我还发现，与仅使用Canvas相比，processing.js在性能方面有点慢(特别是如果您使用Processing语言解析字符串，而不是使用javascriptAPI)。与处理包装器相比，我个人更

  9. go - 为什么我必须使用 core.CreateIntVarFromTo 才能让这个数独解算器工作？ - 2

    我正在使用Golanggofd包来提供约束满足解决方案来解决数独问题。我创建以下内容packagemainimport("bitbucket.org/gofd/gofd/core""bitbucket.org/gofd/gofd/propagator""bitbucket.org/gofd/gofd/labeling""encoding/json""io/ioutil""fmt")varROWS=[]string{"A","B","C","D","E","F","G","H","I"}varCOLS=[]int{1,2,3,4,5,6,7,8,9}varSQUARE1=[]string

  10. java - 在此用例中使用反射来解决我不允许修复的设计问题是否合理？ - 2

    以下用例是否被认为有理由进行反射(reflection)？有一堆从XSD生成的类(目前项目中有数百个)代表各种响应。所有这些响应都包含通用响应数据结构，而不是对其进行扩展。当超时等事件发生时，我只需要将单个字符串设置为特定值。如果这些类扩展了公共(public)响应结构，我总是可以设置此响应代码而无需反射，但事实并非如此。因此我为我的服务编写了简单的实用程序，它使用反射来获取String字段的setter方法并使用预定义的值调用它。我唯一知道的替代方法是使用特定于类的方法，这些方法会复制代码来处理超时，唯一的区别是返回的Response类。protectedThandleTimeout

随机推荐