1.4.5 USACO wormhole （搜索，枚举）

╰半夏微凉° 2023-05-28 11:16 9阅读 0赞

**Wormholes**

Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm, each located at a distinct point on the 2D map of his farm (the x,y coordinates are both integers).

According to his calculations, Farmer John knows that his wormholes will form N/2 connected pairs. For example, if wormholes A and B are connected as a pair, then any object entering wormhole A will exit wormhole B moving in the same direction, and any object entering wormhole B will similarly exit from wormhole A moving in the same direction. This can have rather unpleasant consequences.

For example, suppose there are two paired wormholes A at (1,1) and B at (3,1), and that Bessie the cow starts from position (2,1) moving in the +x direction. Bessie will enter wormhole B \[at (3,1)\], exit from A \[at (1,1)\], then enter B again, and so on, getting trapped in an infinite cycle!

| . . . .
       | A > B .      Bessie will travel to B then
       + . . . .      A then across to B again

Farmer John knows the exact location of each wormhole on his farm. He knows that Bessie the cow always walks in the +x direction, although he does not remember where Bessie is currently located.

Please help Farmer John count the number of distinct pairings of the wormholes such that Bessie could possibly get trapped in an infinite cycle if she starts from an unlucky position. FJ doesn't know which wormhole pairs with any other wormhole, so \\fBfind all the possibilities (i.e., all the different ways that N wormholes could be paired such that Bessie can, in some way, get in a cycle\\fP). Note that a loop with a smaller number of wormholes might contribute a number of different sets of pairings to the total count as those wormholes that are not in the loop are paired in many different ways.

### PROGRAM NAME: wormhole ###

### INPUT FORMAT: ###

<table> 
 <tbody> 
  <tr> 
   <td>Line 1:</td> 
   <td>The number of wormholes, N.</td> 
  </tr> 
  <tr> 
   <td>Lines 2..1+N:</td> 
   <td>Each line contains two space-separated integers describing the (x,y) coordinates of a single wormhole. Each coordinate is in the range 0..1,000,000,000.</td> 
  </tr> 
 </tbody> 
</table>

### SAMPLE INPUT (file wormhole.in): ###

4
    0 0
    1 0
    1 1
    0 1

### INPUT DETAILS: ###

There are 4 wormholes, forming the corners of a square.

### OUTPUT FORMAT: ###

<table> 
 <tbody> 
  <tr> 
   <td>Line 1:</td> 
   <td>The number of distinct pairings of wormholes such that Bessie could conceivably get stuck in a cycle walking from some starting point in the +x direction.</td> 
  </tr> 
 </tbody> 
</table>

### SAMPLE OUTPUT (file wormhole.out): ###

### OUTPUT DETAILS: ###

If we number the wormholes 1..4 as we read them from the input, then if wormhole 1 pairs with wormhole 2 and wormhole 3 pairs with wormhole 4, Bessie can get stuck if she starts anywhere between (0,0) and (1,0) or between (0,1) and (1,1).

| . . 
       d c . 
       a b .

Here is a list of all the pairings, annotated with their wormhole results:  
(a b) (c d) -- Bessie loops (a b) if she is on that line  
(a c) (b d) -- Bessie loops b->d->c->a->b ... if she gets caught  
(a d) (b c)

Only the pairings a-d and b-c allow Bessie to walk in the +x direction from any point in the 2D plane with no danger of cycling.

翻译：[P1444 \[USACO1.3\]虫洞 wormhole][P1444 _USACO1.3_ wormhole]

> 题解：这个题一开始没有想出来，参考的别人的代码。
> 
> 大概的题意是指一个人在+x方向走路，如果遇到匹配的虫洞，就会传送到匹配的虫洞中去，如果这个人回到了原点，说明这个人进入了无限循环（形成了环），这种匹配方式就是一种解。
> 
> 比如：人在X位置，1和2匹配，人往右走到2后直接就传送到了1，然后又继续往右走，这样又回到了原点，所以形成了无线循环。
> 
> 1 X 2
> 
> 本题只需要枚举得到所有的点匹配方式，然后看每种匹配方式是否会造成无限循环（形成环），如果形成了环，解ans++.
> 
> 题目样例（已经排序后的编号）
> 
> 2 4
> 
> 1 3
> 
> 1. 枚举得到所有点的匹配方式
> 
> 可以使用dfs,有点类似于全排列的写法，不同的是在进行两个点匹配时，比如1和3虫洞匹配，代码可以写成：b\[1\]=3,b\[3\]=1.
> 
> 只要b\[i\]!=0,表示1和3已经匹配过了,如果b\[i\]=0,就表示i这个点还没有匹配，就枚举每个还没匹配的点和它进行匹配。
> 
> 题目给的样例有3中匹配方式。
> 
> （1） 1 2匹配，3 4匹配
> 
> （2）1 3匹配，2 4匹配
> 
> （3）1 4 匹配，2 3匹配
> 
> 2. 计算形成环的匹配方式个数
> 
> 接下来就是分别计算a,b,c三种方式是否形成了环。
> 
> 如何判断是否形成了环呢？
> 
> a. 因为人是可以从任意点出发的，所以需要枚举人出发的每个点，看从不同点出发是否会形成环。
> 
> b. 形成环的过程可以进行模拟。假设刚开始人就站在一个虫洞上，直接传送到他匹配的虫洞上面，然后往右走，看看人是否会回到原点，所以需要记录原点的位置，这个过程需要用递归来完成。
> 
> 比如（1）这种情况，人刚开始在1这个位置，然后传送到2上面，然后往右走，到达3，3和4匹配，所以直接传动到4上面，然后往右走，发现不会回到原点，所以这不是我们想要的解。
> 
> 比如（2）这种情况，假设人刚开始在1这个位置，然后直接传送到3, 没有形成环；再假设人在2的位置，然后传送到4，也没有形成环；假设人在3的位置，直接传送到1，然后往右走，又回到了3的位置，所以形成了环，是一种我们想要的解，ans++。

> 这个代码必须要进行排序，因为在判断a\[d\].y == a\[d+1\].y时，只能相距最近的两个点进行判断。（d相当于模拟人走过的路径，现在所在的位置）
> 
> 比如不排序时，虫洞的状态是这样的
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]
> 
> 假设1和2配对，3和4配对。人从x处出发走，如果不排序，x是先到达2这个虫洞的，明显会导致答案错误。实际上x应该先到达3传送到4才对，不会再经过2了。
> 
> 就上面这个图，排序后编号应该为：
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]
> 
> 这样代码就不会错了。

/*
    ID: L
    PROG: wormhole
    LANG: C++
    */
    #include<bits/stdc++.h> 
    using namespace std;
    struct node{
    	int x,y;
    }a[15];//a数组存虫洞的坐标 
    int n; 
    int b[15];//b[i]=x，表示i和x进行了匹配。b[i]=0,表示i点没有匹配的虫洞 
    int ans;//记录形成匹配的方案数 
    bool cmp(node aa, node bb){//先按横坐标从小到大排，横坐标相同按照纵坐标从小到大排 
    	if(aa.y == bb.y) return aa.x < bb.x;
    	else return aa.y < bb.y;
    } 
    
    //begin:表示贝茜开始位置，用来判断是否回到原点
    //p1 = 1: 走的方式到达d点； p1 = 0:从虫洞直接到达d点 
    int f(int num, int d, int begin, int p1) 
    {
    	if(num != 1 && d == begin && p1 == 1) return 1;//用走的方式回到了原点
    	if(p1 == 0)//从虫洞d出来，就往前走，如果前面有虫洞就走过去，没有就返回0 
    	{
    		if(a[d].y == a[d+1].y)  
    			return f(num+1, d+1, begin, 1);
    		else return 0;//没有形成环就返回0 
    	} 
    	if(p1 == 1)
    		return f(num+1,b[d],begin,0);//走到虫洞口了就跳进去 
    } 
    
    bool check()//检查是否会形成环 
    {
    	for(int i = 1; i <= n; ++i)//枚举贝茜从每个点出发，看是否会形成环 
    	{
    		if(f(1,i,i,1) == 1) return 1;//能形成环就返回1 
    	}
    	return 0;
    }
    
    
    void dfs(int x)
    {
    	if(x == n+1){//n个点都匹配完了，就检查是否有环 
    		if(check() == 1) ans++;
    		return ;
    	}
    	if(b[x] == 0)//如果x没有匹配 
    	{
    		for(int i = x+1; i <= n; ++i)//一个一个点的去匹配 
    		{
    			if(b[i] == 0)//如果i没有匹配 
    			{
    				b[i] = x;
    				b[x] = i;//标记，i和x相互匹配 
    				dfs(x+1);//往后搜
    				b[i] = 0;
    				b[x] = 0;//还原 
    			} 
    		} 
    	} 
    	if(b[x] != 0) dfs(x+1);//x匹配了就继续往后搜；
    	return ; 
    }
    
    
    int main()
    {
    	freopen("wormhole.in","r",stdin);
    	freopen("wormhole.out","w",stdout);
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    		cin >> a[i].x >> a[i].y;//x为横坐标，y为纵坐标
    	sort(a+1,a+1+n,cmp);
    	dfs(1);//一个点一个点的进行匹配
    	cout << ans << endl;
      	fclose(stdin);
      	fclose(stdout);
    	return 0;
    } 
    /*
    4
    0 0 
    1 0
    2 0
    0 1
    */

官方给的解答：

The process of solving this problem is described in the video above; the final code is shown below.

#include <iostream>
    #include <fstream>
    using namespace std;
    #define MAX_N 12
    
    int N, X[MAX_N+1], Y[MAX_N+1];
    int partner[MAX_N+1];
    int next_on_right[MAX_N+1];
    
    bool cycle_exists(void)
    {
      for (int start=1; start<=N; start++) {
        // does there exist a cylce starting from start
        int pos = start;
        for (int count=0; count<N; count++)
          pos = next_on_right[partner[pos]];
        if (pos != 0) return true;
      }
      return false;
    }
    
    // count all solutions
    int solve(void) 
    {
      // find first unpaired wormhole
      int i, total=0;
      for (i=1; i<=N; i++) 
        if (partner[i] == 0) break;
    
      // everyone paired?
      if (i > N) {
        if (cycle_exists()) return 1;
        else return 0;
      }
    
      // try pairing i with all possible other wormholes j
      for (int j=i+1; j<=N; j++)
        if (partner[j] == 0) {
          // try pairing i & j, let recursion continue to 
          // generate the rest of the solution
          partner[i] = j;
          partner[j] = i;
          total += solve();
          partner[i] = partner[j] = 0;
        }
      return total;
    }
    
    int main(void)
    {
      ifstream fin("wormhole.in");
      fin >> N;
      for (int i=1; i<=N; i++) fin >> X[i] >> Y[i];
      fin.close();
      
      for (int i=1; i<=N; i++) // set next_on_right[i]...
        for (int j=1; j<=N; j++)
          if (X[j] > X[i] && Y[i] == Y[j]) // j right of i...
    	if (next_on_right[i] == 0 ||
    	    X[j]-X[i] < X[next_on_right[i]]-X[i])
    	  next_on_right[i] = j;
    
      ofstream fout("wormhole.out");
      fout << solve() << "\n";
      fout.close();
      return 0;
    }

[P1444 _USACO1.3_ wormhole]: https://www.luogu.com.cn/problem/P1444
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20230528/0dd1946c98954fd6ab5af641c5725461.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20230528/8b2cb5895abf4858a4f65e8f261717c1.png