pxe
BAN USERSolution using BFS. Running time - length of string * O(V+E)
#include <iostream>
#include <algorithm>
#include <stack>
#include <list>
#include <queue>
#define G 5
using namespace std;
list<int> *nei;
list <char> *out;
void addEdge(){
for(int v=1; v<=26; v++) {
if(v-1 >= 1 && (v-1)%G !=0) nei[v].push_back(v-1);
if(v+1 <= 26 && v%G != 0) nei[v].push_back(v+1);
if(v+G >=1 && v+G <= 26) nei[v].push_back(v+G);
if(v-G >=1 && v-G <= 26) nei[v].push_back(v-G);
}
}
void print(int l){
list<char>::iterator it;
for(int i=0; i<l; i++) {
for( it=out[i].begin(); it!=out[i].end(); it++)
cout<<*it;
}
}
void find(int s, int end, int pos){
bool visited[27] = {false};
int parent[27] = {-1};
queue<int> q;
list<int>::iterator it;
q.push(s);
visited[s] = true;
parent[s] = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(it = nei[cur].begin(); it!=nei[cur].end(); it++){
if(visited[*it] == false) {
visited[*it] = true;
parent[*it] = cur;
if(*it == end) {
out[pos].push_front('!');
while(parent[end] !=0) {
if(parent[end]+1 == end) out[pos].push_front('r');
if(parent[end]-1 == end) out[pos].push_front('l');
if(parent[end]+G == end) out[pos].push_front('d');
if(parent[end]-G == end) out[pos].push_front('u');
end = parent[end];
} return;
}
q.push(*it);
}
}
}
return;
}
int main() {
string s = "up";
nei = new list<int>[27];
out = new list<char>[s.length()];
addEdge();
find(1, s[0]-96, 0);
for(int i =1; i<s.length(); i++){
if(s[i-1]-96 != s[i]-96)
find(s[i-1]-96, s[i]-96, i);
else out[i].push_front('!');
}
print(s.length());
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int main() {
string in[] ={"adsd", "qasdasdb", "ndasdf", "aasddq", "fasda", "deasdn", "oooa"};
int n = 7;
int a[26] ={};
for(int i =0; i<n; i++) {
int s = (in[i][0])-97;
int e = (in[i][(in[i].length()-1)])-97;
a[s]++;
if(s != e) {
a[e]++;
}
}
int count =0;
for(int i =0; i<26; i++){
if(a[i]%2 !=0) count++;
}
if(count == 2) cout<<" YES "<<endl; else cout<<"NO "<<endl;
return 0;
}
The blob has to be a rectangle. I highly doubt this flood fill approach.
- pxe October 23, 2013