寒訓 01/29 基礎班範例代碼 - 社課教學 - 竹園論壇 - 手機版

寒訓 01/29 基礎班範例代碼

看1564|回2|收藏

樓主 ChinHuangLi@FB 只看他
2015-1-29 16:51:50

本帖最後由 domen111 於 2015-1-29 17:01 編輯

[mw_shl_code=cpp,true]#include <stdio.h>
#include <algorithm>
using std::sort;

/*using structure*/
struct BOOK{
      char author[200];
      char name[200];
      int year;
};

BOOK mybook[100];
int rank[128];

void init_rank(void){
      char s[29] = " .XOBCDAFGHUJKLMNIPQRSTEVWYZ";
      for(int i=0;i<28;++i){
            rank[s] = i;
            if( s >= 'A' && s <= 'Z' )
                     rank[s-'A'+'a'] = i;
      }
      rank[0] = -1;
}
int XDrz;

bool string_cmp(char s1[], char s2[]){
      for(int i=0;s1!=0 || s2!=0;++i){
            if( rank[s1] < rank[s2] )
                     return true;
            else if( rank[s1] > rank[s2] )
                     return false;
      }
      return false;
}

bool cmp(BOOK x, BOOK y){
      if( string_cmp(x.author, y.author) )
            return true;
      else if( string_cmp(y.author, x.author) )
            return false;
      if( x.year < y.year ) return true;
      else if( x.year > y.year ) return false;
      if( string_cmp(x.name, y.name) )
            return true;
      else
            return false;
}

int main(){
      init_rank();

      int n;
      char buf[30+100+4+10];

      gets(buf);
      sscanf( buf, "%d", &n);

      for(int i=0;i<n;++i){
            gets(buf);
            int len = 0;
            int j;
            for(j=0;buf[j]!=',';++j)
                     mybook.author[len++] = buf[j];
            j += 2;
            len = 0;
            for(;buf[j]!='(';++j)
                     mybook.name[len++] = buf[j];
            j += 1;
            char number[5];
            for(int k=0;k<4;++k)
                     number[k] = buf[j+k];
            number[4] = 0;
            sscanf( number, "%d", &mybook.year);
      }
      sort( mybook, mybook+n, cmp);

      for(int i=0;i<n;++i){
            printf("%s, %s(%d)\n", mybook.author, mybook.name, mybook.year);
      }

      return 0;
}
[/mw_shl_code]

Zerojudge b240

-1^# Sylveon 只看他
2015-1-31 09:37:13

[mw_shl_code=cpp,true]#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
using namespace std;

int map[9][9];
int N,NN;
bool check()
{
set<int> s;

for(int i=0;i<NN;++i)
{
//line
s.clear();
for(int j=0;j<NN;++j)
{
if( map[j] != 0 )
if( s.find( map[j] ) == s.end() )
s.insert(map[j]);
else
return false;
}
//row
s.clear();
for(int j=0;j<NN;++j)
{
if( map[j] != 0 )
if( s.find( map[j] ) == s.end() )
s.insert(map[j]);
else
return false;
}
}
//block
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
{
s.clear();
for(int k=0;k<N*N;++k)
{
int I = i*N + k/N;
int J = j*N + k%N;
if( map[I][J] != 0 )
if( s.find( map[I][J] ) == s.end() )
s.insert(map[I][J]);
else
return false;
}
}
return true;
}
bool dfs(int id)
{

if( id == NN*NN )
{
if( check() )
{
for(int i=0;i<NN;++i)
{
for(int j=0;j<NN;++j)
cout<<map[j]<<' ';
cout<<'\n';
}
return true;
}
return false;
}
int I = id/NN;
int J = id%NN;
if( map[I][J] )
return dfs(id+1);
for(int i=1;i<=NN;++i)
{
map[I][J]=i;
if( check() )
if( dfs(id+1) )
return true;
map[I][J]=0;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>N)
{
NN=N*N;
for(int i=0;i<NN;++i)
{
for(int j=0;j<NN;++j)
{
cin>>map[j];
}
}
if(!dfs(0))
cout<<"NO SOLUTION\n";
}
return 0;
}
[/mw_shl_code]

3^# jill880829 只看他
2015-2-2 19:04:30

學長您好  我不曉得為甚麼我改成多冊資輸入+每輸入一回會自動更新紀錄的值，但上傳ZJ是WA，請求協助
[mw_shl_code=cpp,true]#include<iostream>
using namespace std;
int n,sudoku[9][9],N;
int ok[9][9][9];
void init_ok(void)
{
      for(int i=0;i<9;i++)
      {
            for(int j=0;j<9;j++)
            {
                     for(int k=0;k<9;k++) ok[j][k]=0;
            }
      }
}
void modify(int x,int y,int i,int w)
{
      for(int j=0;j<N;j++)
      {
            ok[y][j]+=w;
            ok[j][x]+=w;
      }
      int a=(y/n)*n;
      int b=(x/n)*n;
      for(int l=a;l<a+n;l++)
      {
            for(int m=b;m<b+n;m++)
            {
                     ok[l][m]+=w;
            }
      }
}
bool solve(void)
{
      int z_min=10,x,y,a,b;
      for(int i=0;i<N;i++)
      {
            for(int j=0;j<N;j++)
            {
                     if(sudoku[j]==0)
                     {
                              int z=0;
                              for(int k=0;k<N;k++)
                              {
                                    if(ok[j][k]==0) z++;
                              }
                              if(z_min>z)
                              {
                                    y=i;
                                    x=j;
                                    z_min=z;
                              }
                     }
            }
      }
      if(z_min==10) return true;
      if(z_min==0) return false;
      else
      {
            for(int i=0;i<N;i++)
            {
                     if(ok[y][x]==0)
                     {
                              sudoku[y][x]=i+1;
                              modify(x,y,i,1);
                              if(solve()) return true;
                              else
                              {
                                    sudoku[y][x]=0;
                                    modify(x,y,i,-1);
                              }
                     }
            }
            return false;
      }
}
int main()
{
      while(cin>>n)
      {
            N=n*n;
            init_ok();
            for(int i=0;i<N;i++)
            {
                     for(int j=0;j<N;j++)
                     {
                              cin>>sudoku[j];
                     }
            }
            for(int i=0;i<N;i++)
            {
                     for(int j=0;j<N;j++)
                     {
                              if(sudoku[j]!=0)
                              {
                                    modify(j,i,sudoku[j]-1,1);
                              }
                     }
            }
            if(solve()==false) cout<<"NO SOLUTION\n";
            else
            {
                     for(int i=0;i<N;i++)
                     {
                              for(int j=0;j<N;j++) cout<<sudoku[j]<<' ';
                              cout<<"\n";
                     }
            }
      }
      return 0;
}
[/mw_shl_code]

愛用插入代碼...

By Sylveon