題目的意思是找到兩行在兩列處相等，主要要做的是記錄某個值是否重復出現過。
經過思考，我的思路是：每一列用一個unordered_map<string,vector<int>>記錄單詞出現的行數，對于某一行中的兩列，如果有兩個元素在同一其他行出現了重復，則可以輸出結果
例如，第4行的第1個元素在1 3 5 6行都出現了重復，第4行的第2個元素在2 3行出現了重復，則r1 = 3; r2 = 4; c1 = 1; c2 =2;
每一行用一個數據結構保存每一列在哪些行出現了重復，如果某一行被重復了兩次，則說明不滿足PNF，輸出結果。
為了保存每一行中出現重復的列，我們可以使用兩種數據結構，一種是數組，一種是unordered_map，保存的鍵值對<key, val>的含義是，本行的val列在key行出現了重復。
數組每一行需要清空，復雜度是O(n)，鍵值對的插入的復雜度是O(n)（每一次是常數，最多插入n次），總復雜度是O(n^2)
使用unordered_map的復雜度每一行也是O(n)，但是常數會更大一些。
讀入可以一個一個讀，如果嫌棄復雜可以將所有的,變成\n然后一行一行讀，我使用的是C++的正則表達式庫regex，挺好用的。
兩種數據結構的實現代碼如下：
數組
#include <iostream>
#include <unordered_map>
#include <array>
#include <vector>
#include <regex>
#include <string>using namespace std;namespace {constexpr int MAXN = 1e4 + 5;constexpr int MAXM = 1e1 + 5;array<int, MAXN> exists;array<unordered_map<string, vector<int>>, MAXM> dict;int n, m;const string YES = "YES";const string NO = "NO";string line, word;regex r("([^,]*),");bool flag;int r1, r2, c1, c2;
}int main() {while (cin >> n >> m) {fill(dict.begin(), dict.end(), unordered_map<string, vector<int>>());//讀取空行getline(cin, line);flag = false;for (int i = 1; i <= n; ++i) {getline(cin, line);if (flag) continue;fill(exists.begin(), exists.begin() + i, 0);line.push_back(',');int j = 1;for (sregex_iterator it(line.begin(), line.end(), r), end_it; it != end_it; ++it, ++j) {word = it->str(1);
// cout << word << " ";auto &exist = dict[j][word];for (auto k : exist) {if (exists[k] > 0) {r1 = k; r2 = i;c1 = exists[k]; c2 = j;flag = true;break;} else {exists[k] = j;}}if (flag) break;dict[j][word].push_back(i);}
// cout << "\n";}if (flag) {cout << NO << "\n"<< r1 << " " << r2 << "\n"<< c1 << " " << c2 << "\n";} else {cout << YES << "\n";}}
}
unordered_map
#include <iostream>
#include <unordered_map>
#include <array>
#include <vector>
#include <regex>
#include <string>
#include <set>using namespace std;namespace {constexpr int MAXN = 1e4 + 5;constexpr int MAXM = 1e1 + 5;unordered_map<int, int> exists;array<unordered_map<string, vector<int>>, MAXM> dict;int n, m;const string YES = "YES";const string NO = "NO";string line, word;regex r("([^,]*),");bool flag;int r1, r2, c1, c2;
}int main() {while (cin >> n >> m) {fill(dict.begin(), dict.end(), unordered_map<string, vector<int>>());//讀取空行getline(cin, line);flag = false;for (int i = 1; i <= n; ++i) {getline(cin, line);if (flag) continue;exists.clear();line.push_back(',');int j = 1;for (sregex_iterator it(line.begin(), line.end(), r), end_it; it != end_it; ++it, ++j) {word = it->str(1);
// cout << word << " ";auto &exist = dict[j][word];for (auto k : exist) {if (exists.count(k) > 0) {r1 = k; r2 = i;c1 = exists[k]; c2 = j;flag = true;break;} else {exists[k] = j;}}if (flag) break;dict[j][word].push_back(i);}
// cout << "\n";}if (flag) {cout << NO << "\n"<< r1 << " " << r2 << "\n"<< c1 << " " << c2 << "\n";} else {cout << YES << "\n";}}
}
提交以后發現，還是使用數組快一點，畢竟常數比較小
看了書以后發現書中采用的是完全不同的思路，不過把字符串首先哈希成數字這個思想我覺得挺重要，對上面的代碼也是一種優化。以后遇到對這種復雜數據結構的映射處理都應該想到這種哈希方法。
然后遍歷每兩列，將每一行的兩個的值加入unordered_map，如果出現重復則輸出。
復雜度是O(nm^2)，按道理來講比上面的代碼會快很多，但是實際提交卻比上面的還慢，不清楚為什么，覺得OJ的測評也挺奇怪的。
經過思考，我覺得上面O(n^2)的算法中，每一行的復雜度在實際數據中應該比O(n)小很多，導致算法大概就是O(n)的，所以速度更快。
#include <iostream>
#include <unordered_map>
#include <array>
#include <vector>
#include <regex>
#include <string>
#include <set>using namespace std;namespace {constexpr int MAXN = 1e4 + 5;constexpr int MAXM = 1e1 + 5;array<array<int, MAXM>, MAXN> dict;class StrHash {unordered_map<string, int> hash;int idx = 0;public:int operator ()(const string &s);};int StrHash::operator()(const string &s) {if (hash.count(s)) return hash[s];return hash[s] = idx++;}class IntHash {int len = 0;public:IntHash(int _len):len(_len) {}int operator() (int a, int b) {return a * len + b;}};int n, m, len;regex r("([^,]*),");string line;bool flag;int r1, r2, c1, c2;unordered_map<int, int> record;
}int main() {ios::sync_with_stdio(false);while (cin >> n >> m) {flag = false;IntHash intHash(n * m);StrHash strHash;getline(cin, line);for (int i = 0; i < n; ++i) {getline(cin, line);line.push_back(',');int j = 0;for (sregex_iterator it(line.begin(), line.end(), r), end_it; it != end_it; ++it, ++j) {
// cout << it->str(1) << endl;dict[i][j] = strHash(it->str(1));}}int word;for (int i = 0; i < m; ++i) {for (int j = 0; j < i; ++j) {record.clear();for (int k = 0; k < n; ++k) {word = intHash(dict[k][i], dict[k][j]);if (record.count(word) > 0) {flag = true;r1 = record[word] + 1;r2 = k + 1;c1 = j + 1;c2 = i + 1;break;} else {record[word] = k;}}if (flag) break;}if (flag) break;}if (flag) {cout << "NO\n"<< r1 << " " << r2 << "\n"<< c1 << " " << c2 << "\n";} else {cout << "YES\n";
//}}
}
