Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Why wa?

Posted by roof at 2006-09-25 17:40:04 on Problem 1128
```#include<iostream>
using namespace std;
const int MININT = -100000; // 0x80000000; // 最小整形值，以VC为准
const int MAXINT = 100000; //0x7fffffff; // 最大整形值，以VC为准
const int MAX = 50;
const int MAXL = 300;
char bd[MAX][MAX]; // 棋盘状态
int line, row; // 棋盘的行数和列数
bool useds[MAXL]; // 辅助变量，表示该字母是否被使用
typedef struct
{
// 字母矩形上下左右边界值
int up, down, left, right;
}Border;
Border borders[MAXL]; // 某字母在棋盘的边界情况
char letters[MAX * MAX]; // 棋盘中所有字母
int letlen; // letters的长度
char answer[MAX * MAX]; // 题目所要答案
void scanBorders(); // 读取各个字母在棋盘的边界情况
void scanLetters(); // 获取letters信息

int main()
{
while(cin >> line >> row)
{
scanBorders();
scanLetters();
}
return 0;
}
{
for(int i = 0; i < line; i++)
for(int j = 0; j < row; j++)
cin >> bd[i][j];
return ;
}
void scanBorders()
{
int i, j;
char ch;
for(i = 0; i < MAXL; i++)
{
borders[i].up = borders[i].left = MAXINT;
borders[i].down = borders[i].right = MININT;
}
for(i = 0; i < line; i++)
for(j = 0; j < row; j++)
{
ch = bd[i][j];
if(i < borders[ch].up) borders[ch].up = i;
if(j < borders[ch].left) borders[ch].left = j;
if(i > borders[ch].down) borders[ch].down = i;
if(j > borders[ch].right) borders[ch].right = j;
}
return ;
}
void scanLetters()
{
char ch;
memset(useds, false, sizeof(useds));
useds['.'] = true;
letlen = 0;
for(int i = 0; i < line; i++)
for(int j = 0; j < row; j++)
{
ch = bd[i][j];
if(!useds[ch])
{
useds[ch] = true;
letters[letlen++] = ch;
}
}
return ;
}
bool findout(int ch)
{
char bdch;
int u = borders[ch].up, d = borders[ch].down;
int l = borders[ch].left, r = borders[ch].right;
int inow, jnow;
inow = u;
for(jnow = l; jnow <= r; jnow++)
{
bdch = bd[inow][jnow];
if(bdch != ch && !useds[bdch]) return false;
}
inow = d;
for(jnow = l; jnow <= r; jnow++)
{
bdch = bd[inow][jnow];
if(bdch != ch && !useds[bdch]) return false;
}
jnow = l;
for(inow = u; inow <= d; inow++)
{
bdch = bd[inow][jnow];
if(bdch != ch && !useds[bdch]) return false;
}
jnow = r;
for(inow = u; inow <= d; inow++)
{
bdch = bd[inow][jnow];
if(bdch != ch && !useds[bdch]) return false;
}
return true;
}
{
char ch;
int stack[MAX * MAX];
int stlen = 0;
memset(useds, false, sizeof(useds));
for(int i = 0; i < letlen; i++)
for(int j = 0; j < letlen; j++)
{
ch = letters[j];
// cout << "try " << ch << endl; //t
if(!useds[ch] && findout(ch))
{
//	cout << "findout " << ch << "!" << endl; //t
useds[ch] = true;
stack[stlen++] = ch;
}
}
for(i = stlen - 1; i >= 0; i--)
answer[stlen - 1 - i] = stack[i];
return ;
}```

Followed by: