P1549 棋盤問(wèn)題（2）

?

搜索||打表

#include<cstdio> #include<cstring> #include<iostream> #include<cstring> #include<cmath> #include<cstdlib>using namespace std;int n,p[105][105],an[11][11],hang,lie,ans[11][11]; bool vi[105];void print(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",ans[i][j]);puts("");} }void scz(){int han=0,li=0;for(int i=1;i<=n;i++) han+=an[1][i],li+=an[i][1];if(han>hang||li>lie) return;hang=han,lie=li;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=an[i][j]; }void dfs(int x,int y){if(y==n+1){int sum=0;if(x==1&&hang!=1010010) {for(int i=1;i<=n;i++) sum+=an[1][i];if(sum>hang) return;hang=sum;}x++,y=1;}if(x==n+1&&y==1) {scz();print();exit(0);return;}if(y==2&&x==n&&lie!=1010010){int sum=0;for(int i=1;i<=n;i++) sum+=an[i][1];if(sum>lie) return;lie=sum;}if(x==1||y==1){for(int i=1;i<=n*n;i++){if(vi[i]) continue;int z=an[x][y-1],s=an[x-1][y];if(z&&!p[z][i]) continue;if(s&&!p[s][i]) continue;an[x][y]=i;vi[i]=1;dfs(x,y+1);an[x][y]=0;vi[i]=0;}}else {for(int i=n*n;i>=1;i--){if(vi[i]) continue;int z=an[x][y-1],s=an[x-1][y];if(z&&!p[z][i]) continue;if(s&&!p[s][i]) continue;an[x][y]=i;vi[i]=1;dfs(x,y+1);an[x][y]=0;vi[i]=0;}} }bool tp(int x){for(int i=2;i<=sqrt(x);i++) if(x%i==0) return false;return true; }void yu(){for(int i=1;i<=n*n;i++){for(int j=1;j<=n*n;j++){if(tp(i+j)) p[i][j]=1;} } }int main() {scanf("%d",&n);if(n==1) printf("NO\n");else{hang=lie=1010010;yu();vi[1]=1;an[1][1]=1;dfs(1,2);if(hang==1010010) cout<<"NO\n";else print();}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/song-/p/9669106.html

總結(jié)

以上是生活随笔為你收集整理的洛谷——P1549 棋盘问题（2）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。