読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 2058 : Moduic Squares

AOJ

問題リンク:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2058

問題概要:
3*3のsquareと1つの値modがあたえられる
squareの各列の和%modとsquareの各行の和%modとsquareの対角線の和%modがすべて等しいものの数を出力せよ

使用した言語:C++

解法:
実際に全通り試した
map怖い

コード:

#include<iostream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<map>
#include<cassert>
#include<deque>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int ans;
map<vector<int>,bool> exist;
bool check(vector<int>& box);

void dfs(int p,vector<int>& box,int bit)
{
  if(p == 10)
    {
      ans += check(box)?1:0;
      return;
    }
  
  if(box[p])
    {
      dfs(p+1,box,bit);
      return;
    } 
  /*
  if(exist[box])
    return;
  exist[box] = true; 
  */
  for(int j=1;j<=10;j++)
    {
      if((bit >> j) & 1)
	continue;
      box[p] = j;
      dfs(p+1,box,bit|(1<<j));
      box[p] = 0;
    }


}

int main()
{
  while(1)
    {
      vector<int> box(10);
      ans = 0;
      exist.clear();
      int bit = 0;
      bool F = true;
      rep(i,10)
	{
	  cin >> box[i];
	  bit |= (1 << box[i]);
	  if(box[i] != -1)
	    F = false;	  
	}
      
      if(F)
	break;
      bit &= (((1<<20)-1)-1);
      dfs(0,box,bit);
      cout <<ans << endl;
   
    }
  return 0;
}

bool check(vector<int>& g)
{
  int module = g[9]; 
  int sum = (g[0]+g[1]+g[2])%module;
  if((g[3]+g[4]+g[5])%module != sum || (g[6]+g[7]+g[8])%module != sum)
    return false;

  if((g[0]+g[3]+g[6])%module != sum || (g[1]+g[4]+g[7])%module != sum || (g[2]+g[5]+g[8])%module != sum)
    return false;

  if((g[0]+g[4]+g[8])%module != sum || (g[2]+g[4]+g[6])%module != sum)
    return false;

  return true;
  
}