OJ Board

Code: Select all

#include <stdio.h>
#define isL(x) ((x) >= 'A' && (x) <= 'Z')
#define isBetter(p1,p2) (sol1[p1] > sol1[p2] || (sol1[p1] == sol1[p2] && sol2[p1] < sol2[p2]))
#define NMAX 55

int n, m;
char map[NMAX][NMAX];
char u[NMAX][NMAX];

int soln;
int sol1[NMAX*NMAX];
char sol2[NMAX*NMAX];

void swapp(int i, int j)
{
  int aux;
  aux = sol1[i]; sol1[i] = sol1[j]; sol1[j] = aux;
  aux = sol2[i]; sol2[i] = sol2[j]; sol2[j] = aux;
}

void hup(int pos)
{
  int p = pos/2;
  if(!p)
    return;
  if(isBetter(p, pos))
  {
    swapp(p, pos);
    hup(p);
  }
}

void hdown(int pos)
{
  int max = pos;
  do
  {
    pos = max;
    if(2*pos <= soln)
      if(isBetter(pos, 2*pos))
        max = 2*pos;
    if(2*pos < soln)
      if(isBetter(max, 2*pos+1))
        max = 2*pos+1;
    if(max == pos)
      return;
    swapp(pos, max);
  } while(1);
}

void hsort()
{
  int tmp = soln;
  while(soln > 1)
  {
    swapp(soln, 1);
    soln--;
    hdown(1);
  }
  soln = tmp;
}

int fill(int y, int x, char ch)
{
  if(map[y][x] != ch || u[y][x])
    return 0;
  u[y][x] = 1;
  return (1 + fill(y-1,x, ch) + fill(y+1,x, ch) + fill(y,x-1, ch) + fill(y,x+1, ch));
}

void addobj(char ch, int val)
{
  soln++;
  sol1[soln] = val;
  sol2[soln] = ch;
  hup(soln);
}

void solve()
{
  int i, j, aux;
  memset(u, 0, sizeof(u));
  soln = 0;
  for(i = 1; i <= n; i++)
    for(j = 1; j <= m; j++)
      if(!u[i][j] && isL(map[i][j]))
        addobj(map[i][j], fill(i, j, map[i][j]));
  hsort();
}

void show()
{
  int i;
  for(i = 1; i <= soln; i++)
    printf("%c %d\n", sol2[i], sol1[i]);
}

int main()
{
  int i, j, k = 0;
  scanf("%d %d\n", &n, &m);
  while(n || m)
  {
    printf("Problem %d:\n", ++k);
    for(i = 1; i <= n; i++)
    {
      for(j = 1; j <= m; j++)
        scanf("%c", &map[i][j]);
      scanf("\n");
    }
    solve();
    show();
    scanf("%d %d\n", &n, &m);
  }
  return 0;
}

Code: Select all

50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..............AAAAA...............................
..............AAAAA...............................
..............AAAAA...............................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.............A.A.A.A.A.A.A.A.A.A..................
..............A.A.A.A.A.A.A.A.A...................
...............A.A.A.A.A.A.A.A....................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
50 50
A.................................................
.A................................................
..A...............................................
...A..............................................
....A.............................................
.....A............................................
......A...........................................
.......A..........................................
........A.........................................
.........A........................................
..........A.......................................
...........A......................................
............A.....................................
.............A....................................
..............A...................................
...............A..................................
................A.................................
.................A................................
..................A...............................
...................A..............................
....................A.............................
.....................A............................
......................A...........................
.......................A..........................
........................A.........................
.........................A........................
..........................A.......................
...........................A......................
............................A.....................
.............................A....................
..............................A...................
...............................A..................
................................A.................
.................................A................
..................................A...............
...................................A..............
....................................A.............
.....................................A............
......................................A...........
.......................................A..........
........................................A.........
.........................................A........
..........................................A.......
...........................................A......
............................................A.....
.............................................A....
..............................................A...
...............................................A..
................................................A.
.................................................A
3 50
AAAAAAAABAAAA.....................................
.AAAAAAAABAAAA....................................
..AAAAAAAABAAAA...................................
1 50
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX
1 26
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0 0

Code: Select all

Problem 1:
Problem 2:
A 15
Problem 3:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 4:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 5:
A 24
A 12
B 1
B 1
B 1
Problem 6:
A 1
A 1
B 1
B 1
C 1
C 1
D 1
D 1
E 1
E 1
F 1
F 1
G 1
G 1
H 1
H 1
I 1
I 1
J 1
J 1
K 1
K 1
L 1
L 1
M 1
M 1
N 1
N 1
O 1
O 1
P 1
P 1
Q 1
Q 1
R 1
R 1
S 1
S 1
T 1
T 1
U 1
U 1
V 1
V 1
W 1
W 1
X 1
X 1
Y 1
Z 1
Problem 7:
A 1
B 1
C 1
D 1
E 1
F 1
G 1
H 1
I 1
J 1
K 1
L 1
M 1
N 1
O 1
P 1
Q 1
R 1
S 1
T 1
U 1
V 1
W 1
X 1
Y 1
Z 1

Code: Select all

Problem 1:
Problem 2:
A 15
Problem 3:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 4:
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
Problem 5:
A 25
A 12
B 1
B 1
B 1
Problem 6:
A 1
A 1
B 1
B 1
C 1
C 1
D 1
D 1
E 1
E 1
F 1
F 1
G 1
G 1
H 1
H 1
I 1
I 1
J 1
J 1
K 1
K 1
L 1
L 1
M 1
M 1
N 1
N 1
O 1
O 1
P 1
P 1
Q 1
Q 1
R 1
R 1
S 1
S 1
T 1
T 1
U 1
U 1
V 1
V 1
W 1
W 1
X 1
X 1
Y 1
Z 1
Problem 7:
A 1
B 1
C 1
D 1
E 1
F 1
G 1
H 1
I 1
J 1
K 1
L 1
M 1
N 1
O 1
P 1
Q 1
R 1
S 1
T 1
U 1
V 1
W 1
X 1
Y 1
Z 1

Code: Select all

#include <iostream>
using namespace std;
#include <cstring>

typedef struct
{
	char cc;
	int num;
}hode;

hode h[251];
char m[51][51];
char flag[51][51];
int count;
int x,y;

void input()
{
	int i,j;
	for(i=0;i<x;i++)
		for(j=0;j<y;j++)
		{
			cin>>m[i][j];
			flag[i][j]=true;
		}
	count=0;
}

void dfs(int i,int j,char c)
{
	if(i-1>=0 && flag[i-1][j] && m[i-1][j]==c)
	{
		h[count].num++;
		flag[i-1][j]=false;
		dfs(i-1,j,c);
	}

	if(j-1>=0 && flag[i][j-1] && m[i][j-1]==c)
	{
		h[count].num++;
		flag[i][j-1]=false;
		dfs(i,j-1,c);
	}

	if(i+1<x && flag[i+1][j] && m[i+1][j]==c)
	{
		h[count].num++;
		flag[i+1][j]=false;
		dfs(i+1,j,c);
	}

	if(j+1<y && flag[i][j+1] && m[i][j+1]==c)
	{
		h[count].num++;
		flag[i][j+1]=false;
		dfs(i,j+1,c);
	}

	return ;
	
}

int main()
{
	int i,j;
	int kase;
	kase=1;

	while(cin>>x>>y && x && y)
	{
		input();
		for(i=0;i<x;i++)
		{
			for(j=0;j<y;j++)
			{
				if(flag[i][j] && m[i][j]!='.')
				{
					h[count].cc=m[i][j];
					h[count].num=1;
					flag[i][j]=false;
					dfs(i,j,m[i][j]);
					count++;
				}
			}
		}
		
		hode t;
		for(i=0;i<count-1;i++)
			for(j=0;j<count-i-1;j++)
			{
				if((h[j].num < h[j+1].num) || (h[j].num == h[j+1].num && h[j].cc > h[j+1].cc))
				{
					t=h[j];
					h[j]=h[j+1];
					h[j+1]=t;
				}
			}
		cout<<"Problem "<<kase++<<":"<<endl;
		for(i=0;i<count;i++)
		{
			cout<<h[i].cc<<" "<<h[i].num<<endl;
		}
	}
	return 0;
}

Code: Select all

5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
25 33
.................................
.................................
.................................
.................................
.................................
.................................
....AAAAA.....AAAA.........AAAAA.
......AAAAAAAAAAAAAAAAAAA.AAA.AAA
.....AABBBBBBBBAAAAAA...A.AAA..AA
...AAABAAABBBAAAAAA...AAA..AAA..A
..AABAAA...AAAA.....AAA.....AA..A
.AAABBBBAAAAA.....AAA........A.AA
BBBBBAAAAA.......AAA........AA...
BBBAAAAA........AAA........AAAA..
AAAAAA.........AA.........AAAAAA.
BAAA..........AA.......AAAAABBAA.
BBAAAA.......AA......AAAABBBBBBAA
BBBBAAAA.....AA.....AAABBBBBBBBAA
BBBBBBAAAA...AA....AAABBBBBBBBAAB
AAAAAAAAAA...AAA...AABBBBBBBAAABB
AAAAAAAAAA....AA...AABBAAAAAABBBB
...AAAAAA.....AAA.AAABBBBBBBBBBBB
.....AAA........AA..AAABBBBBBBBBB
....AAA..........AAA..AAAABBBBBBB
AAAAA..............AAAAAAABBBBBBB
5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
0 0

Code: Select all

Problem 1:
C 4
A 3
B 3
D 3
A 2
E 1
Problem 2:
A 263
B 76
B 13
B 13
B 11
B 1
5 5
Problem 3:
C 4
A 3
B 3
D 3
A 2
E 1

Code: Select all

//code removed

Code: Select all

#include<stdio.h>
void flood_it(char x,int i,int j);
char a[55][55];
int s;
struct {
	char id;
	int fre;
}srt[3000];

int main()
{
	int i,j,x,y,r,k,pos;
	char c;
	k=0;
//	freopen("plz.txt","r",stdin);
	while(scanf("%d%d\n",&x,&y)==2&&(x!=0&&y!=0)){
		printf("Problem %d:\n",++k);
		for(i=1;i<=x;i++){
			for(j=1;j<=y;j++)scanf("%c",&a[i][j]);
			scanf("\n");
		}
		r=-1;
		for(i=1;i<=x;i++){
			for(j=1;j<=y;j++){
				if((a[i][j]>64&&a[i][j<91])||(a[i][j]>96&&a[i][j]<123)){
					srt[++r].id=a[i][j];
					s=0;
					flood_it(a[i][j],i,j);
					srt[r].fre=s;
				}
			}
		}
		for(i=0;i<r;i++){
			pos=i;
			for(j=i+1;j<=r;j++)if(srt[pos].fre<srt[j].fre)pos=j;
			if(i!=pos){
				srt[pos].fre=srt[pos].fre+srt[i].fre;
				srt[i].fre=srt[pos].fre-srt[i].fre;
				srt[pos].fre=srt[pos].fre-srt[i].fre;
				c=srt[pos].id;
				srt[pos].id=srt[i].id;
				srt[i].id=c;
			}
		}
		for(i=0;i<r;i++){
			pos=i;
			for(j=i+1;j<=r;j++)if(srt[pos].id>srt[j].id)pos=j;
			if((i!=pos)&&(srt[pos].fre==srt[i].fre)){
				srt[pos].fre=srt[pos].fre+srt[i].fre;
				srt[i].fre=srt[pos].fre-srt[i].fre;
				srt[pos].fre=srt[pos].fre-srt[i].fre;
				c=srt[pos].id;
				srt[pos].id=srt[i].id;
				srt[i].id=c;
			}
		}
		for(i=0;i<=r;i++){
			printf("%c %d\n",srt[i].id,srt[i].fre);
		}
	}
	return 0;
}
void flood_it(char x,int i,int j){
	if(a[i][j]!=x)return;
	a[i][j]='.';
	++s;
	flood_it(x,i,j+1);
	flood_it(x,i,j-1);
	flood_it(x,i+1,j);
	flood_it(x,i-1,j);
	return;
}