### 分类：ACM_POJ

REPORT POJ1258-Agri-Net

## REPORT POJ1258-Agri-Net

Agri-Net
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 53017 Accepted: 22052
Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

//=======================================================

//=======================================================

```#include <iostream>
#include <string.h>
#define inf 0x3f3f3f3f
#define N 110
using namespace std;
int G[N][N], n;

int prim()
{
int dist[N], visited[N];
int pos, min = inf, result = 0;
memset(visited, 0, sizeof(visited));
visited[1] = 1; pos = 1;
for (int i = 1; i <= n; i++)
if (i != pos) dist[i] = G[pos][i];
for (int i = 1; i<n; i++)
{
min = inf;
for (int j = 1; j <= n; j++)
if (visited[j] == 0 && min > dist[j])
min = dist[j], pos = j;
result += min;
visited[pos] = 1;
for (int j = 1; j <= n; j++)
if (visited[j] == 0 && dist[j]>G[pos][j])
dist[j] = G[pos][j];
}
return result;
}

int main()
{
while (cin >> n)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> G[i][j];
cout << prim() << endl;
}
return 0;
}
```
REPORT POJ2485-Highways

## REPORT POJ2485-Highways

Highways
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 28843 Accepted: 13165
Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
//===================================================
PRIM求最小生成树，求的时候记录当前最小生成树里的最大边

//===================================================

```#include <iostream>
#include <cstdio>
#include <string.h>
#define inf 0x3f3f3f3f
#define MAXN 505
using namespace std;

int dist[MAXN][MAXN];
int n;

int prim()
{
int s = 1, m = 1, min, point, ANS = 0, currentShortest[MAXN];
bool u[501] = { false };
u[s] = true;

memset(currentShortest, inf, sizeof(currentShortest));

while (true)
{
if (m == n)
break;

min = inf;
for (int i = 2; i <= n; i++)
{
if (!u[i] && currentShortest[i] > dist[s][i]) currentShortest[i] = dist[s][i];
if (!u[i] && min>currentShortest[i])
{
min = currentShortest[i];
point = i;

}
}

if (ANS < min) ANS = min;
s = point;
u[s] = true;
m++;
}
return ANS;
}

int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d",&dist[i][j]);
cout << prim() << endl;
}
return 0;
}
```
REPORT POJ1789-Truck History

## REPORT POJ1789-Truck History

Truck History
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 25362 Accepted: 9902
Description

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of company’s history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on.

Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan — i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as
1/Σ(to,td)d(to,td)

where the sum goes over all pairs of types in the derivation plan such that to is the original type and td the type derived from it and d(to,td) is the distance of the types.
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan.

//=========================================================

//=========================================================

```#include <iostream>
#include <string>
#define INF 0x3f3f3f3f
#define MAX 2005
using namespace std;

int N;
string t[MAX];
int d[MAX][MAX];

int calc(int a, int b)
{
int d = 0;
for (int i = 0; i < 7; i++)
if (t[a][i] != t[b][i]) d++;
return d;
}

int prim(void)
{
int startPoint = 1, visitedCount = 1, weight = 0, shortest, flag, shortestDist[MAX];
bool includePoint[MAX];

memset(shortestDist, INF, sizeof(shortestDist));
memset(includePoint, false, sizeof(includePoint));
includePoint[startPoint] = true;

while (true)
{
if (visitedCount == N) break;
shortest = INF;
for (int j = 2; j <= N; j++)
{
if (!includePoint[j] && shortestDist[j] > d[startPoint][j])
shortestDist[j] = d[startPoint][j];
if (!includePoint[j] && shortest > shortestDist[j])
{
shortest = shortestDist[j];
flag = j;
}
}
startPoint = flag;
includePoint[startPoint] = true;
weight += shortest;
visitedCount++;
}
return weight;
}

int main()
{
while (cin >> N && N != 0)
{
for (int i = 1; i <= N; i++)
cin >> t[i];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
{
d[i][j] = calc(i, j);
}
int ans = prim();
cout << "The highest possible quality is 1/" << ans << '.' << endl;
}
}
```
REPORT POJ2240-Arbitrage

## REPORT POJ2240-Arbitrage

Arbitrage
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 21264 Accepted: 9061
Description

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
//========================================

//========================================

```#include <iostream>
#include <string>
#include <map>
#include <string.h>
#define MAXN 100
using namespace std;

typedef struct Edge
{
int u, v;
double cost;
}Edge;
double dis[1005];
int edges, countNode;
Edge edge[5200];
map<string, int> table;

bool Bellman_Ford()
{
for (int i = 0; i < countNode - 1; i++)
{
for (int j = 0; j < edges; j++)
{
if (dis[edge[j].v] < dis[edge[j].u] * edge[j].cost)
{
dis[edge[j].v] = dis[edge[j].u] * edge[j].cost;
}
}
}
for (int i = 0; i < edges; i++)
{
if (dis[edge[i].v] < dis[edge[i].u] * edge[i].cost)
{
return true;
}
}
return false;
}

int main()
{
int F = 0;
while (cin >> countNode&&countNode != 0)
{
F++;
memset(dis, 0x3F, sizeof(dis));
for (int i = 0; i < countNode; i++)
{
string name;
cin >> name;
table.insert(pair<string, int>(name, i));
}
cin >> edges;
for (int i = 0; i < edges; i++)
{
string name1, name2;
double rate;
cin >> name1 >> rate >> name2;
int u = table[name1];
int v = table[name2];
edge[i].u = u;
edge[i].v = v;
edge[i].cost = rate;
}
cout << "Case " << F << ": ";
if (!Bellman_Ford())
cout << "No" << endl;
else
cout << "Yes" << endl;
}
return 0;
}
```
REPORT POJ1125-Stockbroker Grapevine

## REPORT POJ1125-Stockbroker Grapevine

Stockbroker Grapevine
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 34407 Accepted: 19049
Description

Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way.

Unfortunately for you, stockbrokers only trust information coming from their “Trusted sources” This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.

//===========================================

//===========================================

```#include <iostream>
#include <string.h>
#define MAXN 105
using namespace std;
int G[MAXN][MAXN], n;

int floyd()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
{
if (j != k && G[j][k]>G[j][i] + G[i][k])
G[j][k] = G[j][i] + G[i][k];
}
int startPoint, wayCost, min = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
{
wayCost = 0;
for (int j = 1; j <= n; j++)
{
if (i != j && G[i][j]>wayCost) wayCost = G[i][j];
}
if (wayCost<min)
{
min = wayCost;
startPoint = i;
}
}
if (min >= 0x3f3f3f3f)
cout << "disjoint" << endl;
else
cout << startPoint << " " << min << endl;
return 0;
}

int main()
{
while (cin >> n && n != 0)
{
memset(G, 0x3f3f3f3f, sizeof(G));
for (int i = 1; i <= n; i++)
{
int m, target, cost;
cin >> m;
for (int j = 1; j <= m; j++)
{
cin >> target >> cost;
G[i][target] = cost;
}
}
floyd();
}

return 0;
}
```
REPORT POJ2253-Frogger

## REPORT POJ2253-Frogger

Frogger
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 38333 Accepted: 12345
Description

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.

//=====================================================

Floyd搞吧，只是要把Floyd定义的最短路径改为这条路径中最长边的大小。
//=====================================================

```#include <iostream>
#include <cmath>
#include <string.h>
#include <iomanip>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MAXN 1005
using namespace std;
double x[MAXN], y[MAXN];
double graph[MAXN][MAXN];

int main()
{
int n, cases = 0;
while (cin >> n&&n != 0)
{
cases++;
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
double deltaX = x[i] - x[j];
double deltaY = y[i] - y[j];
graph[i][j] = sqrt(deltaX*deltaX + deltaY*deltaY);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
{
graph[j][k] = MIN(graph[j][k], MAX(graph[j][i], graph[i][k]));
}
cout << "Scenario #" << cases << endl;
cout << fixed << setprecision(3) << "Frog Distance = " << graph[0][1] << endl;
cout << endl;
}
return 0;
}
```
REPORT POJ1062-昂贵的聘礼

## REPORT POJ1062-昂贵的聘礼

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 45796Accepted: 13583
Description

//================================================

//================================================

```#include <iostream>
#include <string.h>
using namespace std;
#define MAXN 105
#define MAXNUM 0x3F3F3F3F
int N, M, graph[MAXN][MAXN] = { 0 }, tier[MAXN] = { 0 }, dist[MAXN] = { MAXNUM };
bool visited[MAXN] = { false };

int Dijkstra()
{
int tempNode, tempShortest;
for (int i = 1; i <= N; i++)
dist[i] = graph[0][i];

for (int i = 1; i <= N; i++)
{
tempNode = 0;
tempShortest = MAXNUM;
for (int j = 1; j <= N; j++)
if (!visited[j] && tempShortest > dist[j])
{
tempShortest = dist[j];
tempNode = j;
}
if (tempNode == 0) break;
visited[tempNode] = true;
for (int j = 1; j <= N; j++)
{
if (!visited[j] && graph[tempNode][j] > 0 && dist[j] > dist[tempNode] + graph[tempNode][j])
{
dist[j] = dist[tempNode] + graph[tempNode][j];
}
}
}

return dist[1];
}

int main()
{
int currentPrice, currentTier, minPrice = MAXNUM;
cin >> M >> N;
for (int i = 1; i <= N; i++)
{
int X;
cin >> graph[0][i] >> tier[i] >> X;
for (int j = 0; j < X; j++)
{
int T, V;
cin >> T >> V;
graph[T][i] = V;
}
}

for (int i = 1; i <= N; i++)
{
currentTier = tier[i];
for (int j = 1; j <= N; j++)
{
if (tier[j] > currentTier || currentTier > tier[j] + M)
visited[j] = true;
else visited[j] = false;
}
currentPrice = Dijkstra();
if (currentPrice < minPrice)
minPrice = currentPrice;
}

cout << minPrice << endl;

return 0;
}
```
REPORT POJ3259-Wormholes

## REPORT POJ3259-Wormholes

Wormholes
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 44770 Accepted: 16486
Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself 🙂 .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output

Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output

NO
YES
Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.
Source

USACO 2006 December Gold

//===========================================================

//===========================================================

```#include <iostream>
#include <string.h>
#define MAXN 100
using namespace std;

typedef struct Edge
{
int u, v;
int cost;
}Edge;
int dis[1005], edges, countNode, M, W;
Edge edge[5200];

bool Bellman_Ford()
{
for (int i = 0; i < countNode - 1; i++)
{
for (int j = 0; j < edges; j++)
{
if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost)
{
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
}
}
}
for (int i = 0; i < edges; i++)
{
if (dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
{
return true;
}
}
return false;
}

int main()
{
int F;
cin >> F;
while (F--)
{
cin >> countNode >> M >> W;
memset(dis, 0x3F, sizeof(dis));
edges = 0;
for (int i = 0; i < M; i++)
{
int u, v, w;
cin >> u >> v >> w;
edge[edges].u = u;
edge[edges].v = v;
edge[edges].cost = w;
edges++;
edge[edges].v = u;
edge[edges].u = v;
edge[edges].cost = w;
edges++;
}
for (int i = 0; i<W; i++)
{
int u, v, w;
cin >> u >> v >> w;
edge[edges].u = u;
edge[edges].v = v;
edge[edges].cost = -w;
edges++;
}
if (!Bellman_Ford())
cout << "NO" << endl;
else
cout << "YES" << endl;
}

return 0;
}
```
REPORT POJ1860-Currency Exchange

## REPORT POJ1860-Currency Exchange

Currency Exchange
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 21122 Accepted: 7572
Description

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.
For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 – 0.39) * 29.75 = 2963.3975RUR.
You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B – numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA – exchange rates and commissions when exchanging A to B and B to A respectively.
Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.

//==============================================================

//==============================================================

//==============================================================

```#include <iostream>
#include <string.h>
#define MAXN 205
using namespace std;

int countNode, countEdge, pointStart, edges;
double moneyStart;

typedef struct Edge
{
int u, v;
double rate, cost;
}Edge;
double dis[MAXN];
Edge edge[MAXN];

bool Bellman_Ford()
{
bool flag;
memset(dis, 0, sizeof(dis));
dis[pointStart] = moneyStart;
for (int i = 1; i <= countNode - 1; i++)
{
for (int j = 0; j < edges; j++)
{
if (dis[edge[j].v] < (dis[edge[j].u] - edge[j].cost)*edge[j].rate)
{
dis[edge[j].v] = (dis[edge[j].u] - edge[j].cost)*edge[j].rate;
}
}
}
for (int i = 0; i < edges; i++)
{
if (dis[edge[i].v] < (dis[edge[i].u] - edge[i].cost)*edge[i].rate)
{
return true;
}
}
return false;
}

int main()
{
int a, b;
double rab, rba, cab, cba;
while (cin >> countNode >> countEdge >> pointStart >> moneyStart)
{
edges = 0;
for (int i = 0; i < countEdge; i++)
{
cin >> a >> b >> rab >> cab >> rba >> cba;
edge[edges].u = a;
edge[edges].v = b;
edge[edges].rate = rab;
edge[edges].cost = cab;
edges++;
edge[edges].u = b;
edge[edges].v = a;
edge[edges].rate = rba;
edge[edges].cost = cba;
edges++;
}
if (!Bellman_Ford())
cout << "NO" << endl;
else
cout << "YES" << endl;
}
return 0;
}
```
REPORT POJ2993/2996

## REPORT POJ2993/2996

POJ 2993:http://poj.org/problem?id=2996
POJ 2996:http://poj.org/problem?id=2996

//=====================================

//=====================================

```//POJ 2993
#include<iostream>
#include<string>
using namespace std;

class whit
{
public:
int row;
char col;
char pie;
}ww[16];

class blac
{
public:
int row;
char col;
char pie;
}bb[16];

int main(void)
{
char white[63],black[63];
gets(white);
gets(black);

int x,y,z,r;

int count_w=0;
int count_b=0;
const int length_w=strlen(white);
const int length_b=strlen(black);

for(x=7,y=0;x<length_w;)
if(white[x]>='B' && white[x]<='R')
{
ww[y].pie=white[x];
ww[y].col=white[x+1];
ww[y].row=white[x+2]-'0';
y++;
x+=4;
count_w++;
}
else if(white[x]>='a' && white[x]<='h')
{
ww[y].pie='P';
ww[y].col=white[x];
ww[y].row=white[x+1]-'0';
y++;
x+=3;
count_w++;
}
else
break;

for(x=7,y=0;x<length_b;)
if(black[x]>='B' && black[x]<='R')
{
bb[y].pie=black[x]+32;
bb[y].col=black[x+1];
bb[y].row=black[x+2]-'0';
y++;
x+=4;
count_b++;
}
else if(black[x]>='a' && black[x]<='h')
{
bb[y].pie='p';
bb[y].col=black[x];
bb[y].row=black[x+1]-'0';
y++;
x+=3;
count_b++;
}
else
break;

char chess[9]['i'];

memset(chess,':',sizeof(chess));

for(x=1;x<=7;x+=2)
for(y='a';y<='g';y+=2)
chess[x][y]='.';
for(x=2;x<=8;x+=2)
for(y='b';y<='h';y+=2)
chess[x][y]='.';

for(x=0;x<count_w;x++)
chess[9-ww[x].row][ww[x].col]=ww[x].pie;

for(x=0;x<count_b;x++)
chess[9-bb[x].row][bb[x].col]=bb[x].pie;

cout<<"+---+---+---+---+---+---+---+---+"<<endl;

for(x=1,r=2;x<=7;x+=2,r+=2)
{
cout<<'|';
for(y='a',z='b';y<='g';y+=2,z+=2)
cout<<"."<<chess[x][y]<<".|:"<<chess[x][z]<<":|";
cout<<endl;
cout<<"+---+---+---+---+---+---+---+---+"<<endl;
cout<<'|';
for(y='a',z='b';y<='g';y+=2,z+=2)
cout<<":"<<chess[r][y]<<":|."<<chess[r][z]<<".|";
cout<<endl;
cout<<"+---+---+---+---+---+---+---+---+"<<endl;
}

return 0;
}
```
```POJ2996
#include<iostream>
using namespace std;

class white_piece
{
public:
int row;
char col;
bool flag;
}K,Q,R[3],B[3],N[3];

bool pawn[9]['i']={false};
int PR=0,PB=0,PN=0;

class black_piece
{
public:
int row;
char col;
bool flag;
}k,q,r[2],b[2],n[2],p[8];

int pr=0,pb=0,pn=0,pp=0;

char chess[9]['i'];
int x,z;
char y;
int w_count=0;
int b_count=0;

void judge()
{
if(chess[x][y]=='.' || chess[x][y]==':')
return;
else if(chess[x][y]=='k')
{
k.row=9-x;
k.col=y;
k.flag=true;
b_count++;
return;
}
else if(chess[x][y]=='q')
{
q.row=9-x;
q.col=y;
q.flag=true;
b_count++;
return;
}
else if(chess[x][y]=='r')
{
r[pr].row=9-x;
r[pr++].col=y;
b_count++;
return;
}
else if(chess[x][y]=='b')
{
b[pb].row=9-x;
b[pb++].col=y;
b_count++;
return;
}
else if(chess[x][y]=='n')
{
n[pn].row=9-x;
n[pn++].col=y;
b_count++;
return;
}
else if(chess[x][y]=='p')
{
p[pp].row=9-x;
p[pp++].col=y;
b_count++;
return;
}
else if(chess[x][y]=='K')
{
K.row=9-x;
K.col=y;
K.flag=true;
w_count++;
return;
}
else if(chess[x][y]=='Q')
{
Q.row=9-x;
Q.col=y;
Q.flag=true;
w_count++;
return;
}
else if(chess[x][y]=='R')
{
R[PR].row=9-x;
R[PR++].col=y;
w_count++;
return;
}
else if(chess[x][y]=='B')
{
B[PB].row=9-x;
B[PB++].col=y;
w_count++;
return;
}
else if(chess[x][y]=='N')
{
N[PN].row=9-x;
N[PN++].col=y;
w_count++;
return;
}
else if(chess[x][y]=='P')
{
pawn[9-x][y]=true;
w_count++;
return;
}
}

void Print(void)
{
cout<<"White: ";
if(K.flag)
{
cout<<'K'<<K.col<<K.row;
if(--w_count>0)
cout<<',';
}
if(Q.flag)
{
cout<<'Q'<<Q.col<<Q.row;
if(--w_count>0)
cout<<',';
}

if(PR==2)
if(R[1].row<R[0].row)
{
R[2]=R[0];
R[0]=R[1];
R[1]=R[2];
}
for(x=0;x<PR;x++)
{
cout<<'R'<<R[x].col<<R[x].row;
if(--w_count>0)
cout<<',';
}

if(PB==2)
if(B[1].row<B[0].row)
{
B[2]=B[0];
B[0]=B[1];
B[1]=B[2];
}
for(x=0;x<PB;x++)
{
cout<<"B"<<B[x].col<<B[x].row;
if(--w_count>0)
cout<<',';
}

if(PN==2)
if(N[1].row<N[0].row)
{
N[2]=N[0];
N[0]=N[1];
N[1]=N[2];
}
for(x=0;x<PN;x++)
{
cout<<'N'<<N[x].col<<N[x].row;
if(--w_count>0)
cout<<',';
}

for(x=1;x<=8;x++)
for(y='a';y<='h';y++)
if(pawn[x][y])
{
cout<<y<<x;
if(--w_count>0)
cout<<',';
}

cout<<endl;

cout<<"Black: ";
if(k.flag)
{
cout<<'K'<<k.col<<k.row;
if(--b_count>0)
cout<<',';
}
if(q.flag)
{
cout<<'Q'<<q.col<<q.row;
if(--b_count>0)
cout<<',';
}
for(x=0;x<pr;x++)
{
cout<<'R'<<r[x].col<<r[x].row;
if(--b_count>0)
cout<<',';
}
for(x=0;x<pb;x++)
{
cout<<"B"<<b[x].col<<b[x].row;
if(--b_count>0)
cout<<',';
}
for(x=0;x<pn;x++)
{
cout<<'N'<<n[x].col<<n[x].row;
if(--b_count>0)
cout<<',';
}
for(x=0;x<pp;x++)
{
cout<<p[x].col<<p[x].row;
if(--b_count>0)
cout<<',';
}

cout<<endl;

return;
}

int main()
{
char temp;

for(z=0;z<33;z++)
cin>>temp;

for(x=1;x<=8;x++)
{
cin>>temp;
for(y='a';y<='h';y++)
{
cin>>temp>>chess[x][y]>>temp>>temp;
judge();
}
for(z=0;z<33;z++)
cin>>temp;
}

Print();
return 0;
}
```