| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
自己想的算法(不知道该叫啥),小错误改完之后,0ms AC!感兴趣的可以瞅瞅!(附几组测试数据)#include <iostream>
#include <set>
using namespace std;
multiset<int> s;
multiset<int>::iterator pos;
int n;
int Init(char a[][5],int h,int l)
{
int i,count = 0;
for(i = l + 1;i < n;i++)//行
if(a[h][i] == 'X')
break;
else
count++;
for(i = l - 1;i >= 0;i--)//行
if(a[h][i] == 'X')
break;
else
count++;
for(i = h + 1;i < n;i++)//列
if(a[i][l] == 'X')
break;
else
count++;
for(i = h - 1;i >= 0;i--)//列
if(a[i][l] == 'X')
break;
else
count++;
return count;
}
bool Set(char a[][5],int h,int l)
{
int i;
multiset<int>::iterator pos1;
for(i = l;i < n;i++)//行
if(a[h][i] == 'X')
break;
else{
pos1 = s.find(a[h][i] - '0');
if(pos1 != s.end())
s.erase(pos1);
a[h][i] = ' ';
}
for(i = l - 1;i >= 0;i--)//行
if(a[h][i] == 'X')
break;
else {
pos1 = s.find(a[h][i] - '0');
if(pos1 != s.end())
s.erase(pos1);
a[h][i] = ' ';
}
for(i = h;i < n;i++)//列
if(a[i][l] == 'X')
break;
else {
pos1 = s.find(a[i][l] - '0');
if(pos1 != s.end())
s.erase(pos1);
a[i][l] = ' ';
}
for(i = h - 1;i >= 0;i--)//列
if(a[i][l] == 'X')
break;
else {
pos1 = s.find(a[i][l] - '0');
if(pos1 != s.end())
s.erase(pos1);
a[i][l] = ' ';
}
return true;
}
int main()
{
int i,j,k = 0,count = 0,result = 0;
char map[4][5];
while(cin >> n && n != 0) {
for(i = 0;i < n;i++)
cin >> map[i];
for(i = 0;i < n;i++)
for(j = 0;j < n;j++) {
if(map[i][j] != 'X') {
count = Init(map,i,j);
s.insert(count);
map[i][j] = count + '0';
}
}
while(!s.empty()) {
bool set = false;
pos = s.begin();
int tmp = *pos;
for(i = 0;i < n;i++) {
for(j = 0;j < n;j++) {
if(map[i][j] == 'X')
continue;
if(tmp == map[i][j] - '0') {
set = Set(map,i,j);
result++;
break;
}
}
if(set)
break;
}
}
cout << result << endl;
result = 0;
s.clear();
}
return 0;
}
4
..X.
.X.X
..X.
.X..
7
1
X
0
1
.
1
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator