首页 > ACM题库 > HDU-杭电 > HDU 1278 漂亮面料的设计-BFS-[解题报告] C++
2013
12-04

HDU 1278 漂亮面料的设计-BFS-[解题报告] C++

漂亮面料的设计

问题描述 :

现在的CAD技术已经能够很方便地设计出漂亮的面料,如图(b)所示。图(a)是所对应的组织图,它表示纱线的交织规律,经过分析表明:组织规律可以用一个二维矩阵准确描述出来。

图(a)的描述矩阵为:
0000101111110011000111000110011111101000
0001001111100110000111000011001111100100
0001011111001100001101100001100111110100
0010011110011100001000100001110011110010
0110111100111100011000110001111001111011
1100111001111000110000011000111100111001
1001111011110001110010011100011110111100
0001110111100011100111001110001111011100
0011110111000011000101000110000111011110
0111101110000010001000100010000011101111
1111101100000100001000100001000001101111
1111011000001100010010010001100000110111
1111011000011100110101011001110000110111
1110110000111001100000001100111000011011
1110110001110011001000100110011100011011
1101100011100010000000000010001110001101
1001100111000000010000010000000111001100
0011000110000100100010001001000011000110
0111001100001101000111000101100001100111
1110001000011010000101000010110000100011
1110011000110000001000100000011000110011
1100010001100000001000100000001100010001
1000110011000100010010010001000110011000
0000100110001000110111011000100011001000
0001100100010001100111001100010001001100
0001001000100011001111100110001000100100
0011001001000010001111100010000100100110
0110010010000000011111110000000010010011
1110010100000100111111111001000001010011
1100100000001101111101111101100000001001
1000101000011011111000111110110000101000
0001000000110011111010111110011000000100
0001010001100011110111011110001100010100
0010000011000111110111011111000110000010
0110100110001111101111101111100011001011
1100000100011111001101100111110001000001
1001001000111110011000110011111000100100
0000001001111100111000111001111100100000
0010010011111101110000011101111110010010
0100010111111111110000011111111111010001
1000100111111011100010001110111111001000
根据行业习惯,1表示黑色格子,0表示白色格子;左下角是起点,最下面一行是第一行,最左面一列是第一列;最上面一行的后一行是第一行,反之,第一行的前面一行是最上面一行,同理,第一列的前一列是最右边一列,最右一列的后一列是第一列。最左边的一列从起点开始依次是:10001100001110000011110011111110001100000,仔细观察后发现,可以用6个分数表示:1/3,2/4,3/5,4/2,7/3,2/5;分子表示1的个数,分母表示0的个数,这样的分数称之为“规则”。第二列从起点开始的规律和第一列的规律正好向上差一行,每一列都有和前一列相差的行数,以后都是类似,只是相差不同而已,由相差的行数可得到一个序列:1,1,2,2,2,2,2,1,1,1,1,1,1,3,1,1,1,2,2,1,-1,-2,-2,-1,-1,-1,-3,-1,-1,-1,-1,-1,-1,-2,-2,-2,-2,-2,-1,-1,负数为向下差;进一步分析表明,可以用14个分数简化之,即:1/2,2/5,1/6,3/1,1/3,2/2,1/1,-1/1,-2/2,-1/3,-3/1,-1/6,-2/5,-1/2;分子表示差的值,分母表示这样的差连续有几个,这样的分数称之为“飞数”,如果这样得到的最后一列和第一列不同,则说明不能生成漂亮面料。现在请你设计一个漂亮的面料。

输入:

本题的输入共有5行,第一行是2个整数M,N;第二行是M个整数,表示“规则”的分子;第三行也是M个整数,表示“规则”的分母;其中第二行和第三行是按序对应;第四行是N个整数,表示“飞数”的分子;第五行也是N个整数,表示“飞数”的分母;其中第四行和第五行也是按序对应。输入数据保证生成的矩阵的行和列数不超过200;如果能够生成漂亮面料,则因为最后一列和第一列相同,所以不需输出最后一列;如果不能生成,则输出Can not make beautilful cloth !。

输出:

按照前面题目的描述输出有0和1组成的二维矩阵。

样例输入:

6  14
1  2  3  4  7  2
3  4  5  2  3  5
1  2  1  3  1  2  1  -1  -2  -1  -3  -1  -2  -1
2  5  6  1  3  2  1   1   2   3   1   6   5   2

样例输出:

参见前面的例子。

HDU-1278-逃离迷宫

http://acm.hdu.edu.cn/showproblem.php?pid=1728

不好想,参考别的代码写的,题目要求转弯的次数不能超过k,BFS,从一个方向搜到底

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
int n1,n2,k;
char map[105][105];
int visit[105][105];
struct node
{
	int x;
	int y;
	int turn;
};
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int go(int x,int y)
{
	if(1<=x&&x<=n1&&1<=y&&y<=n2&&map[x][y]=='.')
	return 1;
	return 0;
}
void bfs(node s1,node s2)
{
	queue<node>q;
	node st,ed;
	int i,nextx,nexty;
	memset(visit,0,sizeof(visit));
	st.x=s1.x;
	st.y=s1.y;
	st.turn=-1;
	q.push(st);
	while(!q.empty())
	{
		st=q.front();
		q.pop();
		for(i=0;i<4;i++)
		{
			nextx=st.x+dir[i][0];
			nexty=st.y+dir[i][1];
			while(go(nextx,nexty))
			{
				if(!visit[nextx][nexty])
				{
					visit[nextx][nexty]=1;
					ed.x=nextx;
					ed.y=nexty;
					ed.turn=st.turn+1;
					if(ed.x==s2.x&&ed.y==s2.y&&ed.turn<=k)
					{
						printf("yes\n");
						return;
					}
					q.push(ed);
				}
				nextx+=dir[i][0];
				nexty+=dir[i][1];
			}
		}
	}
	printf("no\n");
	return;
}
int main()
{
	int t,i,j;
	node s1,s2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n1,&n2);
        for(i=1;i<=n1;i++)
		{
			getchar();
			for(j=1;j<=n2;j++)
		    scanf("%c",&map[i][j]);
		}
		scanf("%d%d%d%d%d",&k,&s1.y,&s1.x,&s2.y,&s2.x);
	    if(s1.y==s2.y&&s1.x==s2.x)
		printf("yes\n");
		else
		bfs(s1,s2);
	}
	return 0;
}


,
  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?