The main idea of the topic :B[i, j] It means how many larger numbers are around it , Can it be used B Array constructs a A Array , If you can't output “NO SOLUTION”.

analysis : The data scale is relatively small , You can directly enumerate the values of each point .

The code is as follows :

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std; const int MAXN = ; int dir[][][] = {{},{},{{},{,},{,},{,},{,}},
{{},{,},{,,},{,},{,,},{,,,},{,,},{,},{,,},{,}}};
int near[][][] = {{},{},{{},{},{},{},{,}},{{},{},{},{},{},{,},{,},{},{,},{,}}};
int B[MAXN], A[MAXN], ok, N; bool nBigger(int k)
{
int i, cnt = , zero=; for(i=; dir[N][k][i]; i++)
{
if(A[k] < A[dir[N][k][i]])
cnt++;
if(!A[dir[N][k][i]])
zero++;
} if(cnt > B[k])
return false;
if(cnt+zero < B[k])
return false;
return true;
}
void DFS(int k)
{
int i, j; if(k == N*N+)
ok = ; if(ok)return ; for(i=; i<MAXN; i++)
{
A[k] = i;
if(nBigger(k) == false)
continue;
for(j=; near[N][k][j]; j++)
{
if(!nBigger(near[N][k][j]))
break;
} if(near[N][k][j] == )
DFS(k+); if(ok)return ;
} A[k] = ;
} int main()
{
scanf("%d", &N); for(int i=; i<=N; i++)
for(int j=; j<=N; j++)
scanf("%d", &B[(i-)*N+j]); DFS(); if(!ok)
printf("NO SOLUTION\n");
else
{
for(int i=; i<=N; i++)
for(int j=; j<=N; j++)
printf("%d%c", A[(i-)*N+j], j==N?'\n':' ');
} return ;
}

Shtirlits - SGU 125( Search for ) More articles about

  1. SGU 125 Shtirlits Search for + Feasibility pruning

    500ms time limit 406ms Water pass …… Direct enumeration must time out , Need pruning . Enumerate the elements of each lattice , Check whether the upper left corner and upper grid meet the conditions , If not, you don't have to search down . stay here   See a better way :  Enumerate which phase each lattice is ...

  2. sgu 125 Shtirlits dfs difficulty :0

    125. Shtirlits time limit per test: 0.25 sec. memory limit per test: 4096 KB There is a checkered fi ...

  3. SGU 125.Shtirlits

    The time limit :0.25s Space restriction :4M The question : Yes N*N Matrix (n<=3), For all i,j<=n Yes G[i][j]<=9, Definition f[i][j] by G[i][j] The number of four sides greater than its number (F[i][ ...

  4. ACM Violent search questions Topic arrangement

    UVa 129 Krypton Factor Note the output format , Compare pit Dad . Each time we have to deal with it to get rid of the easy string , Count the number of difficult strings . #include<iostream> #include<vec ...

  5. Today, SGU 5.18

    SGU 125 The question : Give you an array b[i][j], Express i,j How many numbers are bigger around it , Ask if you can construct a a rectangular Harvest :dfs  + prune Line by line dfs, Then the first line enumerates 0-9, The next line judges the current selection ...

  6. ElasticSearch5 stay Ubuntu System installation and Java call

    ElasticSearch Is a new member of the open source search platform , Real time data analysis artifact . It can be understood as a database for searching , Can provide search function . Compare relational databases , It has the following similar relationship : Relational database database surface That's ok Column Elast ...

  7. Intellij Idea course

    Intellij Idea course [ Cover installation . To configure . common problem & skill .Maven.Git.Tomcat. Shortcut key . Project configuration, etc ] Catalog introduction ............................. ...

  8. Centroid - SGU 134( Tree search )

    The main idea of the topic : Here's a tree for you , Every point in the tree has a value , The value of this point is equal to the son with the most points among all the sons , The lowest value is called the center of gravity , Center of gravity , And all the points that are equal to the center of gravity , Output in ascending order . analysis : It's a simple search tree , Find the biggest ...

  9. SGU 520 Fire in the Country( game + Search for )

    Description This summer's heat wave and drought unleashed devastating wildfires all across the Earth ...

Random recommendation

  1. Asp.Net_Mvc_@Html.xxx() An extension of

    /// <summary> /// Generate category drop-down - List box , Select the specified item /// </summary> /// <param name="html"&g ...

  2. C++ A topological sort

    Amway is a better blog ... The principle and implementation of topological sorting I thought I would fight if I understood the principle , I didn't expect that because I didn't practice it manually ... I don't really remember the principle .... A question HDU The naked problem of topology HDU 3342 My topology ...

  3. ubuntu Set up IP, Set up the gateway

    1. Check if it can be connected , Just use ping command ping gateway   It's always realistic in the beginning unreachable 2. Set up IP sudo ifconfig eth0 133.133.133.190 netmask ...

  4. T-SQL Basics ( stored procedure , trigger || note 0808)

    One : stored procedure 1. Use EXEC Calling stored procedure 2. System stored procedure is based on SP_ start ,SP_ProcedureName.: Example :EXEC sp_columns TableName  View column information   Extended stored procedure ...

  5. The first 3 Chapter Struts2 frame --2、 complete Struts2 Framework application examples

    1. Build a Dynamic Web project, Project name :UserManager, hold Struts2 Necessary JAR Copy to project WEB-INF/lib Under the table of contents 2. modify web.xml file , stay web.xml writing ...

  6. Netbeans7.4 The structures, struts2.3.16

    One : The required jar The package is as follows : stay WEB-INF Create a new one in the directory lib The folder will jar Copy the package inside : Here we should pay attention to jar Package import lib It's not in the catalog yet , Here with MyEclipse Different . Right click Properties on the project -> ...

  7. Ionic The project uses Aurora push

    Ionic The project uses Aurora push -android   about Ionic The project uses the message push service ,Ionic The official provided ngCordova project , What's in this one is for angularjs Packaged message push service ( Official documents ) ...

  8. Thinking about an interview question (C# Value type and reference type )

    Some year, some month , I went to interview an outsourcing project of CMB , After I came to the interview place , The interviewer gave me a test paper , There are only two questions in the paper , One of them is like this : Read the following procedure class Program { struct Point { p ...

  9. pc There are several ways to adapt the font size

    $(window).resize(function ()// Bound to this event in the window {  var whdef = 100/1920;// Express 1920 The design of , Use 100PX The default value of  var wH ...

  10. [k8s]k8s To configure nfs Do backend storage &amp; More configurations nginx Shared memory &amp;&amp;statefulset To configure

    All nodes are installed nfs yum install nfs-utils rpcbind -y mkdir -p /ifs/kubernetes echo "/ifs/kubernetes 192.1 ...