結果
問題 | No.283 スライドパズルと魔方陣 |
ユーザー |
![]() |
提出日時 | 2016-09-26 00:12:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,505 bytes |
コンパイル時間 | 2,251 ms |
コンパイル使用メモリ | 179,160 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 06:36:48 |
合計ジャッジ時間 | 6,382 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 38 WA * 1 |
コンパイルメッセージ
main.cpp: In function 'bool check(VVI, VI, int, int)': main.cpp:93:31: warning: 'gc' may be used uninitialized [-Wmaybe-uninitialized] 93 | return ((abs(sr-gr)+abs(sc-gc))%2)==(cnt%2); | ~~^~~ main.cpp:80:12: note: 'gc' was declared here 80 | int gr,gc; | ^~ main.cpp:93:20: warning: 'gr' may be used uninitialized [-Wmaybe-uninitialized] 93 | return ((abs(sr-gr)+abs(sc-gc))%2)==(cnt%2); | ~~^~~ main.cpp:80:9: note: 'gr' was declared here 80 | int gr,gc; | ^~ main.cpp: In function 'int main()': main.cpp:127:13: warning: 'sr' may be used uninitialized [-Wmaybe-uninitialized] 127 | if(check(res,pos,sr,sc)==false){ | ~~~~~^~~~~~~~~~~~~~~ main.cpp:107:9: note: 'sr' was declared here 107 | int sr,sc,bg=0,ed=n-1; | ^~ main.cpp:127:13: warning: 'sc' may be used uninitialized [-Wmaybe-uninitialized] 127 | if(check(res,pos,sr,sc)==false){ | ~~~~~^~~~~~~~~~~~~~~ main.cpp:107:12: note: 'sc' was declared here 107 | int sr,sc,bg=0,ed=n-1; | ^~
ソースコード
#include<bits/stdc++.h> using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; #define fin "\n" inline void init(int n,VVI &c){ c.resize(n); for(auto &v:c){ v.resize(n); for(auto &u:v)u=0; } } void twotwo(int n,VVI &c){ init(n,c); int q=n/4; for(int i=0;i<q;i++){ for(int j=0;j<q;j++){ c[i*4][j*4]=(i*4)*n+(j*4)+1; c[i*4][j*4+1]=n*n-((i*4)*n+(j*4+1)); c[i*4][j*4+2]=n*n-((i*4)*n+(j*4+2)); c[i*4][j*4+3]=(i*4)*n+(j*4+3)+1; } for(int j=0;j<q;j++){ c[i*4+1][j*4]=n*n-((i*4+1)*n+(j*4)); c[i*4+1][j*4+1]=(i*4+1)*n+(j*4+1)+1; c[i*4+1][j*4+2]=(i*4+1)*n+(j*4+2)+1; c[i*4+1][j*4+3]=n*n-((i*4+1)*n+(j*4+3)); } for(int j=0;j<q;j++){ c[i*4+2][j*4]=n*n-((i*4+2)*n+(j*4)); c[i*4+2][j*4+1]=(i*4+2)*n+(j*4+1)+1; c[i*4+2][j*4+2]=(i*4+2)*n+(j*4+2)+1; c[i*4+2][j*4+3]=n*n-((i*4+2)*n+(j*4+3)); } for(int j=0;j<q;j++){ c[i*4+3][j*4]=(i*4+3)*n+(j*4)+1; c[i*4+3][j*4+1]=n*n-((i*4+3)*n+(j*4+1)); c[i*4+3][j*4+2]=n*n-((i*4+3)*n+(j*4+2)); c[i*4+3][j*4+3]=(i*4+3)*n+(j*4+3)+1; } } } void odd(int n,VVI& c){ init(n,c); int x=0,y=n/2; c[x][y]=1; for(int i=2;i<=n*n;i++){ int _x=(x+n-1)%n,_y=(y+1)%n; if(c[_x][_y])x=(x+1)%n; else x=_x,y=_y; c[x][y]=i; } } void lux(int n,VVI &c){ int magic[][2][2]={{{4,1},{2,3}},{{1,4},{2,3}},{{1,4},{3,2}}}; init(n,c); VVI mark; int half=n/2; init(half,mark); for(int j=0;j<half;j++)mark[half/2+1][j]=1; for(int i=(half/2)+2;i<half;i++)for(int j=0;j<half;j++)mark[i][j]=2; mark[half/2][half/2]=1;mark[half/2+1][half/2]=0; VVI mini; odd(n/2,mini); for(int i=0;i<half;i++) for(int j=0;j<half;j++){ mini[i][j]--;mini[i][j]*=4; for(int x=0;x<2;x++) for(int y=0;y<2;y++) c[2*i+x][2*j+y]=mini[i][j]+magic[mark[i][j]][x][y]; } } bool check(VVI res,VI pos,int sr,int sc){ int n=res.size(); int gr,gc; auto ans=res; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ if(res[i][j]==n*n)gr=i,gc=j; ans[i][j]=pos[res[i][j]]; } int cnt=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int r=0;r<n;r++) for(int c=0;c<n;c++) if(i*n+j<r*n+c&&ans[i][j]>ans[r][c])cnt++; return ((abs(sr-gr)+abs(sc-gc))%2)==(cnt%2); } int main(){ int n; VVI res; cin>>n; if(n<=2){ cout<<"impossible"<<fin; return 0; } else cout<<"possible"<<fin; VI pos(n*n+1); VVI input(n,VI(n)); int sr,sc,bg=0,ed=n-1; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ int &u=input[i][j]; cin>>u; if(u==0){ u=n*n; sr=i; sc=j; } pos[u]=i*n+j; } switch(n%4){ case 0:twotwo(n,res);break; case 1:odd(n,res);bg++,ed--;break; case 2:lux(n,res);break; case 3:odd(n,res);break; default: odd(n,res);break; } if(check(res,pos,sr,sc)==false){ for(;bg<ed;bg++,ed--)swap(res[bg],res[ed]); } for(int i=0;i<n;i++){ cout<<res[i][0]; for(int j=1;j<n;j++)cout<<" "<<res[i][j]; cout<<fin; } return 0; }