Chinaunix首页 | 论坛 | 博客

熟睡的企鹅finekill.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zhln

  • 博客访问： 1546766
  • 博文数量： 327
  • 博客积分： 10000
  • 博客等级： 上将
  • 技术积分： 3556
  • 用 户 组： 普通用户
  • 注册时间： 2005-04-05 21:28
个人简介

东黑布衣，流浪幽燕。 真诚善良，值得信赖。

文章分类

全部博文（327）

我的朋友
推荐博文
相关博文
[ACM02] 0503

分类： BSD

2017-06-03 17:04:58


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  5. #define MAXN 15
  6. #define limit(x,y) ((x>=0) && (x<n) && (y>=0) && (y<n))
  7. int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
  8. int n;
  9. int group[4][2*MAXN-1];
  10. int g[4][2*MAXN-1][3];//前两维与上面group一致,后面一维0:未确定 1:确定不放 2:确定放
  11. int board[MAXN][MAXN];
  12. int done;

  14. int color(int x, int y)
  15. {
  16.    int list[MAXN*MAXN][2];//que for bfs
  17.    int t,xx,yy,p,i;
  18.    list[0][0]=x;
  19.    list[0][1]=y;
  20.    board[x][y]=2;
  21.    t=1;p=0;
  22.    while(p<t){
  23.       for(i=0; i<4; i++){
  24.          xx=d[i][0]+list[p][0];
  25.          yy=d[i][1]+list[p][1];
  26.          if(limit(xx,yy) && (board[xx][yy]==0)){
  27.             board[xx][yy]=2;
  28.             list[t][0]=xx;
  29.             list[t][1]=yy;
  30.             t++;
  31.          }
  32.       }
  33.       p++;
  34.    }
  35.    return 0;
  36. }

  38. int enclosed_intersections()
  39. {
  40.    int i,j,k;
  41.    for(i=0; i<n; i++){
  42.       if(board[0][i]==0)
  43.          color(0,i);
  44.       if(board[n-1][i]==0)
  45.          color(n-1,i);
  46.    }

  48.    for(i=1; i<n-1; i++){
  49.       if(board[i][0]==0)
  50.          color(i,0);
  51.       if(board[i][n-1]==0)
  52.          color(i,n-1);
  53.    }

  55.    k=0;//统计封闭交叉点
  56.    for(i=0;i<n;i++){
  57.       for(j=0;j<n;j++){
  58.          if(board[i][j]==0)
  59.             k++;
  60.       }
  61.    }
  62.    return k;
  63. }

  65. int update(int board[MAXN][MAXN])
  66. {
  67.    int i,j,k,l,l1,l2;
  68.    int flag;//标记是否通过推断确定了某些新位置

  70.    /* 根据每行的约束条件进行推断 */
  71.    flag=0;
  72.    for(i=0;i<n;i++){
  73.       if(group[0][i]>g[0][i][2]+g[0][i][0])
  74.          return -1;//目标棋子数不能超过已放棋子+剩余位置数
  75.       //剩余位置都要放
  76.       if((g[0][i][0]>0) && (group[0][i]==g[0][i][2]+g[0][i][0])){
  77.          flag=1;
  78.          for(j=0;j<n;j++){
  79.             if(board[i][j]==-1)
  80.                board[i][j]=1;
  81.          }
  82.       }
  83.       //剩余位置都不能放
  84.       if((g[0][i][0]>0) && (group[0][i]==g[0][i][2])){
  85.          flag=1;
  86.          for(j=0;j<n;j++){
  87.             if(board[i][j]==-1)
  88.                board[i][j]=0;
  89.          }
  90.       }
  91.    }
  92.    if(flag)
  93.       return 1;
  94.    /* 根据每列的约束条件进行判断 */
  95.    for(j=0;j<n;j++){
  96.       if(group[1][j]>g[1][j][2]+g[1][j][0])
  97.          return -1;
  98.       if((g[1][j][0]>0) && (group[1][j]==g[1][j][2]+g[1][j][0])){
  99.          flag=1;
  100.          for(i=0;i<n;i++){
  101.             if(board[i][j]==-1)
  102.                board[i][j]=1;
  103.          }
  104.       }
  105.       if((g[1][j][0]>0) && (group[1][j]==g[1][j][2])){
  106.          flag=1;
  107.          for(i=0;i<n;i++){
  108.             if(board[i][j]==-1)
  109.                board[i][j]=0;
  110.          }
  111.       }
  112.    }
  113.    if(flag)
  114.       return 1;

  116.    /* 根据每条对角线的约束条件进行判断 */
  117.    for(k=0;k<2*n-1;k++){
  118.       if(group[2][k]>g[2][k][2]+g[2][k][0])
  119.          return -1;
  120.       if((g[2][k][0]>0) && (group[2][k]==g[2][k][2]+g[2][k][0])){
  121.          flag=1;
  122.          if(k<=n-1){
  123.             l1=0;
  124.             l2=k;
  125.          }else{
  126.             l1=k-n+1;
  127.             l2=n-1;
  128.          }
  129.          for(l=l1;l<=l2;l++){
  130.             if(board[l][k-l]==-1)
  131.                board[l][k-l]=1;
  132.          }
  133.       }
  134.       if((g[2][k][0]>0) && (group[2][k]==g[2][k][2])){
  135.          flag=1;
  136.          if(k<=n-1){
  137.             l1=0;
  138.             l2=k;
  139.          }else{
  140.             l1=k-n+1;
  141.             l2=n-1;
  142.          }
  143.          for(l=l1;l<=l2;l++){
  144.             if(board[l][k-l]==-1)
  145.                board[l][k-l]=0;
  146.          }
  147.       }
  148.    }
  149.    if(flag)
  150.       return 1;
  151.          
  152.    /* 根据每条反对角线的约束条件进行判断 */
  153.    for(k=0;k<2*n-1;k++){
  154.       if((group[3][k]>g[3][k][2]+g[3][k][0]))
  155.          return -1;
  156.       if((g[3][k][0]>0) && (group[3][k]==g[3][k][2]+g[3][k][0])){
  157.          flag=1;
  158.          if(k<=n-1){
  159.             l1=n-1-k;
  160.             l2=n-1;
  161.          }else{
  162.             l1=0;
  163.             l2=2*n-2-k;
  164.          }
  165.          for(l=l1;l<l2;l++){
  166.             if(board[l][k+l-n+1]==-1)
  167.                board[l][k+l-n+1]=1;
  168.          }
  169.       }
  170.       if((g[3][k][0]>0) && (group[3][k]==g[3][k][2])){
  171.          flag=1;
  172.          if(k<=n-1){
  173.             l1=n-1-k;
  174.             l2=n-1;
  175.          }else{
  176.             l1=0;
  177.             l2=2*n-2-k;
  178.          }
  179.          for(l=l1;l<l2;l++){
  180.             if(board[l][k+l-n+1]==-1)
  181.                board[l][k+l-n+1]=0;
  182.          }
  183.       }
  184.    }
  185.    if(flag)
  186.       return 1;
  187.    return 0;
  188. }

  190. int deduce(int board[MAXN][MAXN])
  191. {
  192.    int i,j,k,flag;
  193.    flag=1;
  194.    while(flag){
  195.       memset(g,0,sizeof(g));
  196.       for(i=0;i<n;i++){
  197.          for(j=0;j<n;j++){
  198.             k=board[i][j];
  199.             g[0][i][k+1]++;
  200.             g[1][j][k+1]++;
  201.             g[2][i+j][k+1]++;
  202.             g[3][j-i+n-1][k+1]++;
  203.          }
  204.       }

  206.       flag=update(board);
  207.       if(flag==-1)
  208.          return -1;
  209.    }
  210.    return 0;
  211. }

  213. int init()//读入数据和完成初始化
  214. {
  215.    int i;
  216.    memset(group,0,sizeof(group));
  217.    memset(board,0xFF,sizeof(board));

  219.    for(i=0;i<n;i++){
  220.       scanf("%d", &group[0][i]);
  221.    }
  222.    for(i=0;i<n;i++)
  223.       scanf("%d", &group[1][i]);
  224.    for(i=0;i<n*2-1;i++)
  225.       scanf("%d", &group[2][i]);
  226.    for(i=0;i<n*2-1;i++)
  227.       scanf("%d", &group[3][i]);

  229.    board[0][0]=group[2][0];
  230.    board[n-1][n-1]=group[2][2*n-2];
  231.    board[n-1][0]=group[3][0];
  232.    board[0][n-1]=group[3][2*n-2];

  234.    deduce(board);
  235.    return 0;
  236. }

  238. int solutionfound(int* x,int* y)
  239. {
  240.    int i,j;
  241.    for(i=0; i<n;i++){
  242.       for(j=0; j<n;j++){
  243.          if(board[i][j]==-1){
  244.             *x=i;
  245.             *y=j;
  246.             return 0;
  247.          }
  248.       }
  249.    }
  250.    return 1;
  251. }

  253. int right()
  254. {
  255.    int i,j,k;
  256.    memset(g,0,sizeof(g));
  257.    for(i=0;i<n;i++){
  258.       for(j=0;j<n;j++){
  259.          k=board[i][j];
  260.          g[0][i][k+1]++;
  261.          g[1][j][k+1]++;
  262.          g[2][i+j][k+1]++;
  263.          g[3][j-i+n-1][k+1]++;
  264.       }
  265.    }

  267.    for(i=0;i<n;i++){
  268.       if(g[0][i][2] != group[0][i])
  269.          return 0;
  270.       if(g[1][i][2] != group[1][i])
  271.          return 0;
  272.    }

  274.    for(i=0;i<2*n-1;i++){
  275.       if(g[2][i][2] != group[2][i])
  276.          return 0;
  277.       if(g[3][i][2] != group[3][i])
  278.          return 0;
  279.    }
  280.    return 1;
  281. }

  283. //依次对棋盘位置搜索,尝试放与不放棋子来找出棋盘布局
  284. int attempt()
  285. {
  286.    int oldboard[MAXN][MAXN];
  287.    int x,y,k;
  288.    if(solutionfound(&x,&y)){
  289.       if(right()){
  290.          done=1;
  291.       }
  292.       return 0;
  293.    }

  295.    memcpy(oldboard,board,sizeof(board));//save original chessboard
  296.    board[x][y]=1;//try to putting chess
  297.    k=deduce(board);
  298.    if(k!=-1){
  299.       attempt();
  300.       if(done)
  301.          return 0;
  302.    }

  304.    memcpy(board,oldboard,sizeof(board));//restore old chessboard
  305.    board[x][y]=0;//try to no putting chess
  306.    k=deduce(board);
  307.    if(k!=-1){
  308.       attempt();
  309.       if(done)
  310.          return 0;
  311.    }
  312.    memcpy(board,oldboard,sizeof(board));
  313.    return 0;
  314. }

  316. int run()
  317. {
  318.    done=0;
  319.    attempt();
  320.    return 0;
  321. }

  323. int main()
  324. {
  325.    int test_case,T;
  326.    freopen("0503in.txt","r",stdin);
  327.    //freopen("0503out.txt","w",stdout);
  328.    //setbuf(stdout,NULL);
  329.    scanf("%d", &T);
  330.    for(test_case=1;test_case<=T;test_case++)
  331.    {
  332.       scanf("%d", &n);
  333.       init();
  334.       run();
  335.       printf("%d\n", enclosed_intersections());
  336.    }
  337.    return 0;
  338. }

Input:
10
1
1
1
1
1
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
5
1 3 2 3 1
0 2 2 2 4
0 0 1 3 0 2 2 1 1
0 0 0 2 3 2 1 2 0
15
15 2 13 13 13 13 13 13 13 13 13 13 13 2 15
15 2 13 13 13 13 13 13 13 13 13 13 13 2 15
1 2 2 2 3 4 5 6 7 8 9 10 11 12 13 12 11 10 9 8 7 6 5 4 3 2 2 2 1
1 2 2 2 3 4 5 6 7 8 9 10 11 12 13 12 11 10 9 8 7 6 5 4 3 2 2 2 1
10
10 2 2 2 2 2 2 2 2 9
10 2 2 2 2 2 2 2 2 9
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0
1 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 1
10
0 8 2 2 2 2 2 2 8 0
0 8 2 2 2 2 2 2 8 0
0 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0
0 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0
10
1 1 1 1 1 1 1 1 1 1
0 0 0 0 10 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
15
2 2 2 2 2 2 2 1 2 2 2 2 2 2 2
2 2 2 2 2 2 2 1 2 2 2 2 2 2 2
1 0 1 0 1 0 1 0 1 0 1 0 1 0 15 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 15 0 1 0 1 0 1 0 1 0 1 0 1 0 1
15
12 6 6 5 5 5 5 5 8 4 4 4 4 4 11
12 6 6 5 4 4 4 9 4 3 4 4 4 4 15
0 2 2 4 0 6 2 2 2 10 0 12 2 2 2 2 7 6 3 3 3 3 2 2 2 2 2 2 1
1 2 2 1 1 2 2 4 4 5 3 6 3 6 1 6 3 7 2 6 2 5 2 4 1 2 2 2 1

Out:
iLyn:acm02 Cute$ time ./0503
0
0
0
3
48
64
36
0
0
122
real    0m0.008s
user    0m0.001s
sys    0m0.003s



阅读(1341) | 评论(0) | 转发(0) |
0

上一篇：[20170524 ADV] Hourglasses

下一篇：lc0048

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6