Virtual Judge

很久以前刷完了 Virtual Judge 上的简单搜索专题，现总结如下： POJ 1321 由于题目的数据范围比较小，可以直接 dfs 暴力。读入时记录每个空位的位置，保存在 pX[] 以及 pY[] 数组中。暴力的时候统计当前处理第几个空格以及当前处理到了第几行即可。 #include <iostream> #include <memory.h> using namespace std; const int MAX = 128; long long ans; int N, K, nCnt; bool pUsed[MAX]; int pX[MAX], pY[MAX]; int pRow[MAX], pCol[MAX]; void dfs(int x, int y); int main() { char dwTmp; while(cin >> N >> K) { if(N == -1 && K == -1) { break; } nCnt = 0; ans = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { cin >> dwTmp; if(dwTmp == '#') { nCnt++; pX[nCnt] = i; pY[nCnt] = j; } } cin.ignore(); } memset(pRow, 0, sizeof(pRow)); memset(pCol, 0, sizeof(pCol)); memset(pUsed, false, sizeof(pUsed)); dfs(1, 0); cout << ans << endl; } return 0; } void dfs(int x, int y) { if(y == K) { ans++; } else { for(int i = x; i <= nCnt; i++) { if(!(pUsed[i] || pRow[pX[i]] || pCol[pY[i]])) { pRow[pX[i]]++; pCol[pY[i]]++; pUsed[i] = true;...

Description His Royal Highness King of Berland Berl XV was a very wise man and had a very accomplished wife, who was aware of the fact, that prominent and outstanding personalities once having written down their names on the pages of glorious History, remain there forever. His Royal Highness King Berl XV experienced an intrinsic, lost nowadays, deep and sincere sense of respect and trust for his beloved spouse. So he decided to acquire a chronicler of his own. Due to the ambiguous nature of misunderstanding and the crying injustice of history to ambiguity, he decided to leave all his royal responsibilities aside and made up his royal mind to find the chronicler, who will make him famous, depicting all his heroic deeds truthfully and gloriously enough. The King assembled the greatest minds of his kingdom at the Academic Chroniclers Meeting (ACM), as he named it, and decided to test their might. The task was to build the Smallest Lexicographical Concatenation (SLC) out of the given $N$ strings. SLC of $N$ strings $s_1,\cdots, s_N$ is the lexicographically smallest their concatenation $s_{i_1} + \cdots + s_{i_N}$, where $ i_1,\cdots, i_N $ is a permutation of integers from 1 through $N$. It’s a great privilege to be a chronicler, so don’t miss your chance and don’t screw it up! Make the king choose you! Input The first line of the input file contains a single integer $N$ ($1\leq N\leq 100$) indicating the number of strings. The following $N$ lines contain $N$ strings,...