URAL 1072. Routing
1. 题目
http://acm.timus.ru/problem.aspx?space=1&num=1072
1072. Routing
Time limit: 1.0 second
Memory limit: 64 MB
There is a TCP/IP net of several computers. It means that:
- Each computer has one or more net interfaces.
- Each interface is identified by its IP-address and a subnet mask — these are two four-byte numbers with a point after each byte. A subnet mask has a binary representation as follows: there are k 1-bits, then — m 0-bits, k+m=8*4=32 (e.g., 212.220.35.77 — is an IP-address and 255.255.255.128 — is a subnet mask).
- Two computers belong to the same subnet, if and only if (IP1 AND NetMask1) = (IP2 AND NetMask2), where IPi and NetMaski — are an IP-address and subnet mask of i-th computer, AND — is bitwise.
- A packet is transmitted between two computers of one subnet directly.
- If two computers belong to different subnets, a packet is to be transmitted via some other computers. The packet can pass from one subnet to another only on computer that has both subnets interfaces.
Your task is to find the shortest way of a packet between two given computers.Input
The first line contains a number N — an amount of computers in the net, then go N sections, describing interfaces of each computer. There is a number K in the first line of a section — that is an amount of interfaces of the computer, then go Klines — descriptions of the interfaces, i.e. its IP-address and a subnet mask. The last line of an input contains two integers — the numbers of the computers that you are to find a way between them.You may assume that 2 ≤ N ≤ 90 and K ≤ 5.Output
The word “Yes” if the route exists, then in the next line the computer numbers passed by the packet, separated with a space. The word “No” otherwise.Sample
input output
Problem Source: Ural State Univerisity Personal Contest Online February’2001 Students Session
2. 思路
给出网络中若干台电脑的信息，包括若干IP地址和子网掩码，求指定两台电脑间的路由是否存在。
建图的时候比较绕，要把同一子网内的电脑都连起来，之后BFS即可。
3.代码
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 90
#define MAX_K 5
typedef char Network[MAX_N + 1][MAX_N + 1];
typedef unsigned char Subnet[MAX_N + 1][MAX_K + 1][4];
void solveE1f();
int inputNetwork(Network network);
void initNetwork(Network network, int computerNum);
int isInSameSubnet(int src, int dest, Subnet subnet, unsigned char ipNum[]);
int equals(unsigned char ip1[], unsigned char ip2[]);
int findPath(int src, int dest, Network network, int computerNum, unsigned char path[]);
void printPath(unsigned char path[], int pathLength);
void printNetwork(Network network, int computerNum);
int main() {
//freopen("test.txt", "r", stdin);
solveE1f();
//system("pause");
return 0;
}
Network network;
void solveE1f() {
int computerNum, src, dest, pathLength;
unsigned char path[MAX_N + 1];
computerNum = inputNetwork(network);
scanf("%d %d", &src, &dest);
//printNetwork(network, computerNum);
pathLength = findPath(src, dest, network, computerNum, path);
if (pathLength == -1) {
printf("No\n");
}
else
printf("Yes\n");
printPath(path, pathLength);
}
Subnet subnet;
unsigned char ipNum[MAX_N + 1];
int inputNetwork(Network network) {
int computerNum, i, j, k;
unsigned int ipAddr[4], mask[4];
scanf("%d", &computerNum);
initNetwork(network, computerNum);
for (i = 1; i <= computerNum; ++i) {
scanf("%d", &ipNum[i]);
for (j = 0; j < ipNum[i]; ++j) {
scanf("%d.%d.%d.%d %d.%d.%d.%d", &ipAddr[3], &ipAddr[2], &ipAddr[1], &ipAddr[0], &mask[3], &mask[2], &mask[1], &mask[0]);
for (k = 0; k < 4; ++k) {
subnet[i][j][k] = ipAddr[k] & mask[k];
}
}
}
for (i = 1; i <= computerNum; ++i) {
for (j = 1; j <= computerNum; ++j) {
if (i == j)
continue;
if (isInSameSubnet(i, j, subnet, ipNum)) {
network[i][j] = 1;
network[j][i] = 1;
}
}
}
return computerNum;
}
void initNetwork(Network network, int computerNum) {
int i, j;
for (i = 0; i < computerNum; ++i) {
for (j = 0; j < computerNum; ++j) {
network[i][j] = 0;
}
}
}
int isInSameSubnet(int src, int dest, Subnet subnet, unsigned char ipNum[]) {
int i, j;
for (i = 0; i < ipNum[src]; ++i) {
for (j = 0; j < ipNum[dest]; ++j) {
if (equals(subnet[src][i], subnet[dest][j])) {
return 1;
}
}
}
return 0;
}
int equals(unsigned char ip1[], unsigned char ip2[]) {
int i;
for (i = 0; i < 4; ++i) {
if (ip1[i] != ip2[i])
return 0;
}
return 1;
}
int findPath(int src, int dest, Network network, int computerNum, unsigned char path[]) {
int i, front = 0, rear = 0, current, queuePos = 0, hasPath = 0;
unsigned char queue[MAX_N + 1], last[MAX_N + 1], visited[MAX_N + 1];
for (i = 1; i <= MAX_N; ++i) {
visited[i] = 0;
}
queue[rear] = src;
last[rear] = 0;
++rear;
visited[src] = 1;
while (front < rear) {
queuePos = front;
current = queue[queuePos];
++front;
if (current == dest) {
hasPath = 1;
break;
}
for (i = 1; i <= computerNum; ++i) {
if (network[current][i] == 1 && visited[i] == 0) {
queue[rear] = i;
last[rear] = queuePos;
++rear;
visited[i] = 1;
}
}
}
if (hasPath == 0)
return -1;
path[0] = current;
queuePos = last[queuePos];
i = 1;
while (1) {
path[i++] = queue[queuePos];
if (queue[queuePos] == src)
return i;
queuePos = last[queuePos];
}
}
void printPath(unsigned char path[], int pathLength) {
int i;
for (i = pathLength - 1; i >= 0; --i) {
printf("%d ", path[i]);
}
printf("\n");
}
void printNetwork(Network network, int computerNum) {
int i, j;
for (i = 1; i <= computerNum; ++i) {
for (j = 1; j <= computerNum; ++j) {
printf("%d ", network[i][j]);
}
printf("\n");
}
}