学步园

//第二次写的

#include <iostream>
#include <map>
#include <queue>
using namespace std;

const int maxn = 100;

char node[maxn];
bool edge[maxn][maxn], visited[maxn];
int n , m;
map<char, int> mm;
queue<char> q;

void Init()
{
	memset(node, '\0', sizeof(node));
	memset(edge, false, sizeof(edge));
	memset(visited, false, sizeof(visited));
}

bool isConnect(const char &a, const char &b)
{
	q.push(a);
	visited[mm[a]] = true;
	
	while(!q.empty())
	{
		char src = q.front();
		q.pop();
		if(src == b)
			return true;
		
		for(int i = 0; i < n; ++i)
		{
			if(edge[mm[src]][mm[node[i]] ] && !visited[mm[node[i]]])
			{
				q.push(node[i]);
				visited[mm[node[i]]] = true;
			}
				
		}
	}
	return false;
}

int main(void)
{
	freopen("1.txt", "r", stdin);
	int N, M, val = 0;
	char from, to;
	Init();
	cout << "nodes num: ";
	cin >> N;
	cout << "nodes: ";
	while(N--)
	{
		cin >> node[n];
		mm[node[n]] = val++;
		n++;	
	}
		
	cout << "edges num: ";
	cin >> M;
	cout << "from to" << endl;
	while(M--)
	{
		cin >> from >> to;
		edge[mm[from]][mm[to]] = true;
	}

	cout << "input two address, A(from) and B(to) :";
	cin >> from >> to;
	
	cout << endl << isConnect(from, to) << endl;
	
	return 0;
}

第一次写的：

#include <iostream>
using namespace std;

int num, m, n;
int reachable[101][101];
bool beenTo[101][101];

bool isReachable(int m[101][101], int src, int des)
{
	int i;
	for (i = 0; i < num; ++i)
	{
		if (m[src][i] && !beenTo[src][i])
		{
			if (i == des)
			{
				return true;
			}
			beenTo[src][i] = true;
			return isReachable(m, i, des);
		}
	}
	return false;
}

int main(void)
{
	int i, j, src, des;
	memset(reachable, 0, sizeof(reachable));
	memset(beenTo, false, sizeof(beenTo));

	for (n = 0; n < 101; n++)
	{
		for (m = 0; m < 101; m++)
		{
			reachable[n][m] = 0;
			beenTo[n][m] = false;
		}
	}
	freopen("in.txt", "r", stdin);
	cin>>num>>src>>des;

	for (i = 0; i < num; ++i)
	{
		for (j = 0; j < num; ++j)
		{
			cin>>reachable[i][j];
		}
	}

	cout<<isReachable(reachable, src, des)<<endl;
	
	fclose(stdin);
	return 0;
}