补题 [2023牛客寒假算法基础集训营1] 本题主要考察了DFS

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

shino是一名喜欢拼图的女高中生，他最喜欢玩的拼图是黄金拼图（指把爱丽丝和九条可怜拼在一起），不过这和本题并没有什么关系。 点我看原番 点我看名场面

某天，shino发现了一款叫做《拼图啊》（PTA）的全新拼图游戏，shino希望你能编写程序帮她开发这个游戏的外挂。

PTA的拼图由 $n\times n$ 个大小为 $1\times1$ 的拼图块组成，每个拼图块都是在正方形的 $1\times1$ 拼图块基础上生成的，生成方法为：对于每一条边，可以选择不变、向里削出一个半圆形的缺口、向外补上一个半圆形的凸出三种操作之一。因此，一个拼图块可以由一个长度为 $4$ 的字符串描述，四个字符分别表示上、右、下、左四条边进行的操作，上述三种操作依次记为 $0,1,2$ 。

例如，下图的左图为一个 $2\times2$ 的拼图。而右图为左图中左上角的一块 $1\times1$ 拼图的字符串描述，由于其上、右、下、左进行的操作分别为不变、凸出、缺口、不变，因此这块拼图对应的字符串为 $0210$ 。
img

每块拼图还有一个制作成本 $p$ ，制作成本正比于面积，而拼图中削去的缺口和补上的凸出面积又相同，因此对于一块削去了 $x$ 个半圆、补上了 $y$ 个半圆的 $1\times1$ 拼图，其制作成本 $p=10-x+y$ 。如上图右图中拼图的成本为 $p=10-1+1=10$ 。

现在，PTA会从所有拼图中随机隐藏一块，并打乱剩下的 $n^2-1$ 块拼图，告诉了你它们的形状对应的字符串表示（由于拼图上绘制了可供辨识的图案，因此给出的拼图形状都是各拼图块正面朝上、未经旋转的正确形状）。

PTA需要你完成这一拼图游戏，还原拼图原来的样子。你需要回答隐藏起来的那块拼图的制作成本来证明你成功完成了拼图

输入描述

输入第一行是一个整数 $T(1\leq T \leq 100)$ ，表示测试用例组数。

对于每组测试用例：

第一行为一个正整数 $n(2 \leq n \leq 20)$ ，表示拼图的大小。

接下来 $n^2-1$ 行，每行一个长度为 $4$ 的字符串，表示一块拼图正面朝上、未经旋转的形状。保证字符串中只含 $0,1,2$ 三种字符。

输入数据保证 $n^2-1$ 块拼图是从一个合法的 $n\times n$ 拼图中按如题面所述的过程获得的。

输出描述

对每组样例输出一个整数，表示你在拼出拼图后所计算出的缺失拼图块的制作成本。

输入

1
2
3
4
5
1
2
0001
0000
0210

输出

1
11

说明

样例即为题目中图片所给的例子，具体来说，输入的三个字符串分别对应图中右上角、右下角、左上角的拼图块。

通过编程将拼图还原，可以发现缺的是左下角的那一块，其形状为 $2000$ ，因此制作成本为 $p=10-0+1=11$ 。

题解

题目解析

依旧是一道诈骗题,想不到当时为什么没有做出来.

我们注意到完整的拼图造价为 $10\cdot n^2$ .显然,如果我们把总造价减去每个拼图的造价,我们完全可以得到那一张没给出拼图的造价.

AC代码

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
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
typedef long long ll;

signed main(){
	CIN;CIN_;
	int T;
	cin >> T;
	while(T--){
		string s;
		int n,sum;
		cin >> n;
		sum = n * n * 10;
		fa(1,n*n-1,1){
			int x=0,y=0;
			cin >> s;
			fa(0,s.size()-1,1){
				if(s[i] == '1') x++;
				if(s[i] == '2') y++;
			}
			sum -= 10 - x + y;
		}
		cout << sum << endl;
	}
	return 0;
}