| 网站首页 | 业界新闻 | 群组 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
雷速体育发帖软件开发QQ118000023C语言培训|一对一辅导|零基础学编程LightningChart 快速先进的.Net图表控件
共有 518 人关注过本帖
标题:方格分割(蓝桥杯)
只看楼主 收藏
troyzyc
Rank: 1
等 级:新手上路
帖 子:106
专家分:0
注 册:2016-7-4
结帖率:57.69%
  问题点数:0  回复次数:2   
方格分割(蓝桥杯)
标题:方格分割(蓝桥杯)

6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。

如图:p1.png, p2.png, p3.png 就是可行的分割法。

试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。

请提交该整数,不要填写任何多余的内容或说明文字。


自己写的程序:从(1,1)开始,dfs走遍所有能走的路径,,结束条件是走了18步,得到的结果却是610;
而正确答案却是509。看网友的程序都是从(3,3)开始走,结束条件是走到边界。一直想不明白自己写的有什么疏漏?


#include<iostream>
#include<algorithm>
using namespace std;

int map[7][7],book[7][7]; //book[][]标记已走的和原点对称的位置
int sum=0;

void dfs(int x,int y,int step)
{
    int s=step; //走到当前步时用的步数
   
    int k,tx,ty;
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    if(s==18)
    {
        sum++;
        return;
    }
   
//    book[x][y]=1;  //走到的位置
//    book[7-x][7-y]=1; //中心对称的位置
   
    for(k=0;k<=3;k++)
    {
        tx=x+next[k][0];
        ty=y+next[k][1];
        if(tx<1 || tx>6 || ty<1 || ty>6)
            continue;
        if(book[tx][ty]!=1) //下一步tx,ty没走过
        {
            book[tx][ty]=1;  //下一步走到tx,ty
            book[7-tx][7-ty]=1;
            dfs(tx,ty,s+1);
            book[tx][ty]=0;
            book[7-tx][7-ty]=0;   
        }
    }
    return ;
}

int main()
{   
    book[1][1]=1;
    book[7-1][7-1]=1;
    dfs(1,1,1);
    cout<<sum<<endl;
    return 0;
}
2018-03-18 09:56
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:45
帖 子:4902
专家分:13909
注 册:2016-10-22
  得分:0 
以下是引用troyzyc在2018-3-18 09:56:37的发言:

自己写的程序:从(1,1)开始,dfs走遍所有能走的路径,,结束条件是走了18步,得到的结果却是610;
而正确答案却是509。看网友的程序都是从(3,3)开始走,结束条件是走到边界。一直想不明白自己写的有什么疏漏?

当然有,因为结束条件不一定是18步~而是走到中心~并且要判断对称的情况~


[此贴子已经被作者于2018-3-18 21:06编辑过]


[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 2018-06-18更~*/[/code]
2018-03-18 20:55
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:45
帖 子:4902
专家分:13909
注 册:2016-10-22
  得分:0 
中心开始出发走到边界判别比较简单~因为起点只有一个,终点可以有很多个~
然而从边界开始起点有很多个,然而终点只有那么一个~

[code]/*~个性签名:弟弟的妹妹叫妹妹,弟弟的姐姐叫姐姐~ 2018-06-18更~*/[/code]
2018-03-18 21:09







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.041629 second(s), 8 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved