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