学步园

题目来源：http://poj.org/problem?id=1033

解题报告：

这道题主要是问，要至少挪几步，才能把各个节点的位置移到应该在的位置，并把要移动的步骤输出。

方法一：

我这里取了数组：

a[i] 代表在i位置放了应该放在a[i]位置的节点

b[i] 代表应该放在i位置的节点现在在b[i]位置

搜索的时候从i=1开始，如果a[i] == i，代表节点位置正确，不用移动

如果a[i] != i，代表位置摆放不正确

这里，又分两种情况：

1) 如果a[i] == 0，说明 i位置现在为空，只要简单的将节点从b[i] 移到 i 就可以了。

2) 如果a[i] != 0，说明i位置现在有节点占着，要先把i位置上的节点放到a[i] 位置，而如果a[a[i]] != 0，则意味着a[i]位置上也有节点占着，要先将a[i]位置上的节点移到正确的位置。于是，我取了一个栈，把这些搜索过程中遇到的节点放入栈中，直到搜索到为空的位置，然后再一次把栈中的节点移到他们正确的位置。当然，也有可能最后出现一个循环，所以，我用了c[i]来记录栈中已有的节点，c[i]=1代表此次搜索，i位置已被访问过，如果出现了循环，则直接从最后的节点往前搜一个空位置，然后把栈顶的节点先移到空位置，等其余节点都在正确的位置时，再把那个节点从空位置已到它应在的正确位置。

方法二：

想了一下，其实用DFS的思路就行了，晚上补充代码和解题报告。

方法一：

#include <iostream>
#include <stack>
using namespace std;

#define N 10000

int main() {
	int a[N] = {0};
	int b[N] = {0};
	int c[N] = {0};
	int n;
	int k;
	cin >> n;
	cin >> k;
	int m = 1;
	for (int i=1; i <=k; i++) {
		int s;
		cin >> s;
		for (int j=1; j <=s; j++) {
			int tmp;
			cin >> tmp;
			a[tmp] = m;
			b[m] = tmp;
			m++;
		}
	}

	stack<int> Q;

	bool needed = false;

	for (int i=1; i<m; i++) {
		int t = i;
		while(a[t]!=t) {
			needed = true;
			if (c[t] == 1)  {
				for (int j =n; j>0; j--) {
					if (a[j] == 0) {
						cout << b[Q.top()] << " " << j << endl;
						b[Q.top()] = j;
						a[j] = Q.top();
						Q.pop();
						break;
					}
				}
				break;
			}
			Q.push(t);
			if (a[t]==0) {
				break;
 			}
			else {
				c[t] = 1;
				t = a[t];
			}
		}
		while(!Q.empty()) {
			int top = Q.top();
			Q.pop();
			cout << b[top] << " " << top << endl;
			a[top]= top;
			a[b[top]] = 0;
			b[top] = top;
		}
		for (int j =0; j < N; j++) {
			c[j] = 0;
		}
	}

	if (!needed){
		cout << "No optimization needed" << endl;
	}


}

附录：

Description

Input

Output

Sample Input

20 3
4 2 3 11 12
1 7
3 18 5 10

Sample Output

2 1
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7