MMT8. 交换查询
描述
小M有一个N*M的方格，行列下标均从0开始。其中有K个方格中有数字，表示为(X, Y)方格中有数字C。对方格有2种操作，交换方格的两行或者交换方格的两列。
小M希望随时能够知道在经过一系列交换之后某一方格中是否含有数字，并且如果有的话，数字是多少。
输入描述
输入数据第一行包含3个整数N, M, K。表示N行M列的方格，并且其中K个方格有数字。输出描述
对于每个询问，输出一个整数表示其答案。示例1
输入:
3 3 2 1 1 1 2 2 2 5 2 1 1 0 0 1 1 0 1 2 1 1 2 2 2
输出:
1 -1 2
说明:
首先有3x3的方格，其中（1，1）有数字1，（2，2）有数字2，即：C++ 解法, 执行用时: 83ms, 内存消耗: 8256KB, 提交时间: 2020-07-28
#include <iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<long, int> dic;
int main(void)
{
int n, m, k, t, x, y, c, Q, a, b, ans;
cin >> n >> m >> k;
int pointX[n], pointY[m];
for (int i = 0; i < n; ++i) {
pointX[i] = i;
}
for (int i = 0; i < m; ++i) {
pointY[i] = i;
}
for(int i = 0; i < k; i++) {
scanf("%d%d%d", &x, &y, &c);
dic[x * m + y] = c;
}
cin >> t;
while(t--) {
scanf("%d%d%d", &Q, &a, &b);
if(Q == 2) {
int key = pointX[a] * m + pointY[b];
int ans;
if(dic.find(key) == dic.end()) ans = -1;
else ans = dic[key];
printf("%d\n", ans);
} else if(Q == 0) {
swap(pointX[a], pointX[b]);
} else {
swap(pointY[a], pointY[b]);
}
}
return 0;
}
C++ 解法, 执行用时: 86ms, 内存消耗: 5324KB, 提交时间: 2020-11-01
#include <iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<long, int> dic;
int main(void)
{
int n, m, k, t, x, y, c, Q, a, b, ans;
cin >> n >> m >> k;
int pointX[n], pointY[m];
for (int i = 0; i < n; ++i) {
pointX[i] = i;
}
for (int i = 0; i < m; ++i) {
pointY[i] = i;
}
for(int i = 0; i < k; i++) {
scanf("%d%d%d", &x, &y, &c);
dic[x * m + y] = c;
}
cin >> t;
while(t--) {
scanf("%d%d%d", &Q, &a, &b);
if(Q == 2) {
int key = pointX[a] * m + pointY[b];
int ans;
if(dic.find(key) == dic.end()) ans = -1;
else ans = dic[key];
printf("%d\n", ans);
} else if(Q == 0) {
swap(pointX[a], pointX[b]);
} else {
swap(pointY[a], pointY[b]);
}
}
return 0;
}
C++ 解法, 执行用时: 94ms, 内存消耗: 8260KB, 提交时间: 2020-09-11
#include <iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<long, int> dic;
int main(void)
{
int n, m, k, t, x, y, c, Q, a, b, ans;
cin >> n >> m >> k;
int pointX[n], pointY[m];
for (int i = 0; i < n; ++i) {
pointX[i] = i;
}
for (int i = 0; i < m; ++i) {
pointY[i] = i;
}
for(int i = 0; i < k; i++) {
scanf("%d%d%d", &x, &y, &c);
dic[x * m + y] = c;
}
cin >> t;
while(t--) {
scanf("%d%d%d", &Q, &a, &b);
if(Q == 2) {
int key = pointX[a] * m + pointY[b];
int ans;
if(dic.find(key) == dic.end()) ans = -1;
else ans = dic[key];
printf("%d\n", ans);
} else if(Q == 0) {
swap(pointX[a], pointX[b]);
} else {
swap(pointY[a], pointY[b]);
}
}
return 0;
}
C++ 解法, 执行用时: 98ms, 内存消耗: 5256KB, 提交时间: 2021-07-22
//* 用hashtable求解，用array会爆内存 *//
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map> // 内部采用的hashtable的数据结构存储，拥有快速检索的功能。
using namespace std;
unordered_map<long, int> dic;
int main()
{
int n, m, k, t, x, y, c, Q, a, b, ans;
cin >> n >> m >> k;
int pointX[n], pointY[m];
for (int i = 0; i < n; ++i) { //row
pointX[i] = i;
}
for (int i = 0; i < m; ++i) { //col
pointY[i] = i;
}
for(int i = 0; i < k; i++) {
scanf("%d%d%d", &x, &y, &c);
dic[x * m + y] = c;
}
cin >> t;
while(t--) {
scanf("%d%d%d", &Q, &a, &b);
if(Q == 2) {
int key = pointX[a] * m + pointY[b];
int ans;
if(dic.find(key) == dic.end()) ans = -1;
else ans = dic[key];
printf("%d\n", ans);
} else if(Q == 0) { // swap row
swap(pointX[a], pointX[b]);
} else { // swap col
swap(pointY[a], pointY[b]);
}
}
return 0;
}
C++ 解法, 执行用时: 99ms, 内存消耗: 5372KB, 提交时间: 2020-10-31
#include <iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<long, int> dic;
int main(void)
{
int n, m, k, t, x, y, c, Q, a, b, ans;
cin >> n >> m >> k;
int pointX[n], pointY[m];
for (int i = 0; i < n; ++i) {
pointX[i] = i;
}
for (int i = 0; i < m; ++i) {
pointY[i] = i;
}
for(int i = 0; i < k; i++) {
scanf("%d%d%d", &x, &y, &c);
dic[x * m + y] = c;
}
cin >> t;
while(t--) {
scanf("%d%d%d", &Q, &a, &b);
if(Q == 2) {
int key = pointX[a] * m + pointY[b];
int ans;
if(dic.find(key) == dic.end()) ans = -1;
else ans = dic[key];
printf("%d\n", ans);
} else if(Q == 0) {
swap(pointX[a], pointX[b]);
} else {
swap(pointY[a], pointY[b]);
}
}
return 0;
}