七桥问题

A.LAl黎

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>          
using namespace std;
//七桥问题邻接矩阵  
int map0[4][4]={
	0,2,2,1,
	2,0,0,1,
	2,0,0,1,
	1,1,1,0
	};

int cnt;

void dfs1(int n,int c)//当前位置，当前层数 
{
	for(int i=0;i<4;i++)//环顾四周，四个目标点
	{
		if(map0[n][i]!=0)
		{
			map0[n][i]--;
			map0[i][n]--;//做标记 
			if(c==7)//是否到达终点 
			{
				cnt++;
			}
			else
			{
				dfs1(i,c+1);
			}
			map0[n][i]++;//回溯//回到上一个点
			map0[i][n]++;  
		}
	} 
}

void qiqiao()
{
	for(int i=0;i<4;i++)
	{
		dfs1(i,1);
	}
}

int main()
{
	qiqiao();
	cout<<cnt; 
    return 0;
}