训练联盟第六场 F. Hopscotch（暴力）

本文主要是介绍训练联盟第六场 F. Hopscotch（暴力），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/15329/F
来源：牛客网

题目描述

There’s a new art installation in town, and it inspires you... to play a childish game. The art installation consists of a floor with an n×n matrix of square tiles. Each tile holds a single number from 1 to k. You want to play hopscotch on it. You want to start on some tile numbered 1, then hop to some tile numbered 2, then 3, and so on, until you reach some tile numbered k. You are a good hopper, so you can hop any required distance. You visit exactly one tile of each number from 1 to k.

What’s the shortest possible total distance over a complete game of Hopscotch? Use the Manhattan distance: the distance between the tile at (x1, y1) and the tile at (x2, y2) is |x1 − x2| + |y1 − y2|.

输入描述:

The first line of input contains two space-separated integers n (1 ≤ n ≤ 50) and k (1 ≤ k ≤ n2),where the art installation consists of an n×n matrix with tiles having numbers from 1 to k.


Each of the next n lines contains n space-separated integers x (1 ≤ x ≤ k). This is the artinstallation. 

输出描述:

Output a single integer, which is the total length of the shortest path starting from some 1 tile andending at some k tile, or −1 if it isn’t possible. 

示例1

输入

复制

10 5
5 1 3 4 2 4 2 1 2 1
4 5 3 4 1 5 3 1 1 4
4 2 4 1 5 4 5 2 4 1
5 2 1 5 5 3 5 2 3 2
5 5 2 3 2 3 1 5 5 5
3 4 2 4 2 2 4 4 2 3
1 5 1 1 2 5 4 1 5 3
2 2 4 1 2 5 1 4 3 5
5 3 2 1 4 3 5 2 3 1
3 4 2 5 2 5 3 4 4 2

输出

复制

5

示例2

输入

复制

10 5
5 1 5 4 1 2 2 4 5 2
4 2 1 4 1 1 1 5 2 5
2 2 4 4 4 2 4 5 5 4
2 4 4 5 5 5 2 5 5 2
2 2 4 4 4 5 4 2 4 4
5 2 5 5 4 1 2 4 4 4
4 2 1 2 4 4 1 2 4 5
1 2 1 1 2 4 4 1 4 5
2 1 2 5 5 4 5 2 1 1
1 1 2 4 5 5 5 5 5 5

输出

复制

-1

暴力即可，用桶存坐标，dis[k, j]表示到编号为k的桶中第j个数的最段路。求解的时候直接三重循环暴力。注意特判k = 1的情况。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, mtx[55][55], dis[2505][2505];
vector<pair<int, int> > a[2505];
long long ans = 1e16;
signed main() {
	cin >> n >> k;
	for(int i = 0; i <= 2500; i++) {
		for(int j = 0; j <= 2500; j++) {
			dis[i][j] = 1e16;
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> mtx[i][j];
			a[mtx[i][j]].push_back(make_pair(i, j));
		}
	}
	for(int i = 1; i <= k; i++) {
		if(!a[i].size()) {
			cout << -1;
			return 0;
		}
	}
	for(int i = 2; i <= k; i++) {
		for(int j = 0; j < a[i - 1].size(); j++) {
			for(int kk = 0; kk < a[i].size(); kk++) {
				if(i != 2) dis[i][kk] = min(dis[i][kk], dis[i - 1][j] + abs(a[i][kk].first - a[i - 1][j].first) + abs(a[i][kk].second - a[i - 1][j].second));
				else dis[i][kk] = min(dis[i][kk], abs(a[i][kk].first - a[i - 1][j].first) + abs(a[i][kk].second - a[i - 1][j].second));
			}
		}
	}
	for(int i = 0; i < a[k].size(); i++) {
		ans = min(ans, dis[k][i]);
	}
	if(k == 1) ans = 0;
	cout << ans;
	return 0;
}

这篇关于训练联盟第六场 F. Hopscotch（暴力）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！