首页 > ACM题库 > HDU-杭电 > HDU 1246 自共轭Ferrers图-DFS-[解题报告] C++
2013
12-04

HDU 1246 自共轭Ferrers图-DFS-[解题报告] C++

自共轭Ferrers图

问题描述 :

Ferrers图是一个自上而下的n层格子,且上层格子数不少于下层格子数。

如上图所示,图中的虚线称为Ferrers图的虚轴。若将图一绕虚轴旋转180°,即将第一行与第一列对调,将第二行与第二列对调,……,这样所得到的图仍为Ferrers图,如下图所示。

这两个图称为一对共轭Ferrers图。有一些Ferrers图,沿虚轴转换后的Ferrers图仍为它本身,也就是说这个Ferrers图关于虚轴对称,那么这个Ferrers图称为自共轭Ferrers图。下图便是一个自共轭Ferrers图。

现在我们的目标是寻找的是大小为n的自共轭Ferrers图的总数。所谓大小为n的自共轭Ferrers图是指由n个方格组成的自共轭Ferrers图。

输入:

输入数据有多行,每行为一个正整数n(1<=n<=300)。表示自共轭Ferrers图的大小为n。

输出:

对应输入的每一个n,输出一行大小为n的自共轭Ferrers图的总数。

样例输入:

1
2
3

样例输出:

1
0
1

 

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

struct node
{
	int x,y;
};
int map[10][10];
node *Q;
int n;
bool isok;
void output()
{
	int i,j;
	for(i=1;i<10;i++)
	{
		for(j=1;j<10;j++)
		{
			if(j>1)printf(" ");
			printf("%d",map[i][j]);
		}
		printf("\n");
	}
}
bool unfind(int x,int y,int k)
{
	int i,j;
	for(i=1;i<10;i++)
	{
		if(map[x][i]==k||map[i][y]==k)return false;
	}
	int tx=(x-1)/3*3+1;
	int ty=(y-1)/3*3+1;
	for(i=tx;i<tx+3;i++)
		for(j=ty;j<ty+3;j++)
			if(map[i][j]==k)return false;
			
			return true;
}
void dfs(int cnt)
{
	if(isok)return;
	int i;
	if(cnt==n)
	{
		isok=true;
		output();
	}
	else
	{
		int tx=Q[cnt].x;
		int ty=Q[cnt].y;
		for(i=1;i<10;i++)
		{
			if(unfind(tx,ty,i))
			{
				map[tx][ty]=i;
				dfs(cnt+1);
				map[tx][ty]=0;
			}
		}
	}
}


int main()
{
	char ch[2];
	int a=0;
	while(scanf("%s",ch)!=EOF)//cin>>ch
	{
		
		Q=new node[81];
		n=0;
		if(ch[0]!='?')
			map[1][1]=ch[0]-'0';
		else
		{
			map[1][1]=0;
			Q[n].x=1;
			Q[n++].y=1;
		}
		int i,j;
		for(i=1;i<10;i++)
		{
			for(j=1;j<10;j++)
			{
				if(i!=1||j!=1)
				{scanf("%s",ch);
				//cin>>ch;
				if(ch[0]!='?')
				{
					int t=ch[0]-'0';
					map[i][j]=t;
				}
				else
				{
					map[i][j]=0;
					Q[n].x=i;
					Q[n++].y=j;
				}
				} 
			}
		}
		if(a)printf("\n");a++;
		isok=false;
		dfs(0);
	}
	return 0;
}

 


,
  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  4. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  5. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }