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

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

AOJ 0078 Magic Square

AOJ

問題文→AIZU ONLINE JUDGE

マスの数を指定して魔法陣を出力する問題

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<map>
using namespace std;
int context[15][15];
void init(){
  for(int i=0;i<15;i++){
    for(int j=0;j<15;j++){
      context[i][j]=0;
    }
  }
}
int main(){
  int n,nowx,nowy;
  while(cin>>n,n){
    init();
    nowx=n/2; nowy=n/2+1;
    context[nowy][nowx]=1;
    for(int i=2;i<=n*n;i++){
      nowx++; nowy++;
      while(true){
	if(nowx>=n) nowx=0;
	if(nowx<0) nowx=n-1;
	if(nowy>=n) nowy=0;
	if(context[nowy][nowx]!=0) nowx--,nowy++;
	if(context[nowy][nowx]==0 && 0<=nowx && nowx<n && 0<=nowy && nowy<n) break;
      }
      context[nowy][nowx]=i;
      //      printf("(%d,%d)\n",nowy,nowx);
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	printf("%4d",context[i][j]);
      }
      cout<<endl;
    }
  }
}

nに制限はあるんだけど、このアルゴリズム結構感動する。
例えば15x15の魔方陣とかも出力できちゃう

15
106 219 92 205 78 191 64 177 50 163 36 149 22 135 8
9 107 220 93 206 79 192 65 178 51 164 37 150 23 121
122 10 108 221 94 207 80 193 66 179 52 165 38 136 24
25 123 11 109 222 95 208 81 194 67 180 53 151 39 137
138 26 124 12 110 223 96 209 82 195 68 166 54 152 40
41 139 27 125 13 111 224 97 210 83 181 69 167 55 153
154 42 140 28 126 14 112 225 98 196 84 182 70 168 56
57 155 43 141 29 127 15 113 211 99 197 85 183 71 169
170 58 156 44 142 30 128 1 114 212 100 198 86 184 72
73 171 59 157 45 143 16 129 2 115 213 101 199 87 185
186 74 172 60 158 31 144 17 130 3 116 214 102 200 88
89 187 75 173 46 159 32 145 18 131 4 117 215 103 201
202 90 188 61 174 47 160 33 146 19 132 5 118 216 104
105 203 76 189 62 175 48 161 34 147 20 133 6 119 217
218 91 204 77 190 63 176 49 162 35 148 21 134 7 120

キレイ