CCF CSP 201512-3 画图

发表于 | 分类于 ，
字数统计: 891 | 阅读时长 ≈ 4

CCF CSP 201512-4 画图

♔题目

♔解题思路

这一题是比较简单的模拟题，只要按照题目要求读入然后进行处理即可。线段部分要注意当纵坐标相等时是横线，当横坐标相等时是竖线，然后注意处理线段相交的地方改为‘+’（‘+’也改为‘+’或跳过）。填充部分用bfs进行遍历，然后遇到线段和边界停止。

虽然简单，但还是有坑点在的。首先是题目中给定的坐标与日常使用数组下标的习惯不符，于是我们对其进行一个转化x’=n-y,y’=x+1。然后要注意**坐标不要写反！**我就是因为这个wa到怀疑人生（不过居然填充字符之前把坐标写反还能拿到90分）

image-20200317184001075

然后在差错的过程中还遇到几个坑点，一个是dfs可能会爆栈，另一个是当一条线段经过一条线段端点时不要将‘+’修改掉。注意以上几点应该就可以解决这个问题了。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
char tu[105][105],flag;
int fx[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int m,n,t;
int xx1,xx2,yy1,yy2;

void xd()
{
	int i;
	scanf("%d%d%d%d",&yy1,&xx1,&yy2,&xx2);
	xx1=n-xx1;
	xx2=n-xx2;
	yy1++;
	yy2++;
	//printf("-%d %d %d %d-\n",xx1,yy1,xx2,yy2);
	if(xx1==xx2)
	{
		if(yy1>yy2) swap(yy1,yy2);
		for(i=yy1;i<=yy2;i++)
		{
			if(tu[xx1][i]=='+' || tu[xx1][i]=='|') tu[xx1][i]='+';
			else tu[xx1][i]='-';
		}
	}
	if(yy1==yy2)
	{
		if(xx1>xx2) swap(xx1,xx2);
		for(i=xx1;i<=xx2;i++)
		{
			if(tu[i][yy1]=='+' || tu[i][yy1]=='-') tu[i][yy1]='+';
			else tu[i][yy1]='|';
		}
	}
}

void dfs(int x,int y)
{
	for(int i=0;i<=3;i++)
	{
		if(x+fx[i][0]>n || x+fx[i][0]<1 || y+fx[i][1]>m || y+fx[i][1]<1) continue;
		if(tu[x+fx[i][0]][y+fx[i][1]]==flag || tu[x+fx[i][0]][y+fx[i][1]]=='-' || tu[x+fx[i][0]][y+fx[i][1]]=='|' || tu[x+fx[i][0]][y+fx[i][1]]=='+') continue;
		//visit[x+fx[i][0]][y+fx[i][1]]=1;
		tu[x+fx[i][0]][y+fx[i][1]]=flag;
		dfs(x+fx[i][0],y+fx[i][1]);
	}
}

void bfs(int x,int y)
{
	queue< pair<int,int> > q;
	q.push(pair<int,int>(x,y));
	int xx,yy;
	while(!q.empty())
	{
		xx=q.front().first;
		yy=q.front().second;
		q.pop();
		for(int i=0;i<=3;i++)
		{
			if(xx+fx[i][0]>n || xx+fx[i][0]<1 || yy+fx[i][1]>m || yy+fx[i][1]<1) continue;
			//if(visit[xx+fx[i][0]][yy+fx[i][1]] || tu[xx+fx[i][0]][yy+fx[i][1]]=='-' || tu[xx+fx[i][0]][yy+fx[i][1]]=='|' || tu[xx+fx[i][0]][yy+fx[i][1]]=='+') continue;
			//visit[xx+fx[i][0]][yy+fx[i][1]]=1;
			tu[xx+fx[i][0]][yy+fx[i][1]]=flag;
			q.push(pair<int,int>(xx+fx[i][0],yy+fx[i][1]));
		}
	}
} 

int main()
{
	int i,j,k;
	scanf("%d%d%d",&m,&n,&t);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++) tu[i][j]='.';
	for(k=1;k<=t;k++)
	{
		//printf("----\n");
		scanf("%d",&j);
		if(j==0)
		{
			xd();
		}
		else if(j==1)
		{
			//memset(visit,0,sizeof(visit));
			scanf("%d %d %c",&yy1,&xx1,&flag);
			xx1=n-xx1;
			yy1++;
			tu[xx1][yy1]=flag;
			//visit[xx1][yy1]=1;
			dfs(xx1,yy1);
			//bfs(xx1,yy1);
		}
//		for(i=1;i<=max(m,n);i++)
//		{
//			for(j=1;j<=max(m,n);j++)
//			{
//				if(tu[i][j]==' ') printf(".");
//				else printf("%c",tu[i][j]);
//			}
//			printf("\n");
//		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			printf("%c",tu[i][j]);
		}
		if(i!=n) printf("\n");
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！