Problem 3003 --Just an Old Puzzle

3003: Just an Old Puzzle

上一题 正确率: $50.00\%$ 下一题
"
Time Limit $2$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $4$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

You are given a 4 × 4 grid, which consists of 15 number cells and an empty cell. 
All numbers are unique and ranged from 1 to 15. 
In this board, the cells which are adjacent with the empty cell can move to the empty cell. 

Your task is to make the input grid to the target grid shown in the 

figure below. 

In the following example (sample input), you can get the target grid in two moves.


Input

The first line contains an integer T (1 <= T <= 10^5) denoting the number of test cases. 
Each test case consists of four lines each containing four space-separated integers, denoting the input grid. 0 indicates the empty cell.

Output

For each test case, you have to print the answer in one line. 
If you can’t get the target grid within 120 moves, then print 'No', else print 'Yes'.

Sample Input复制

2
1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0

Sample Output复制

Yes
No

推荐代码 查看3003 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$41 $ms] intLSY 480558 2019-10-08 22:02:51
内存最少[$0 $KB] 淡意的温柔 590702 2020-06-05 08:33:08
第一AC intLSY 480558 2019-10-08 22:02:51
第一挑战 intLSY 480554 2019-10-08 22:02:05

赛题来源/所属竞赛 2019 Multi-University Training Contest 4 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛