یافتن باگ کد

[sa1378]

سلام
برای این سوال (http://codeforces.com/problemset/problem/475/B) من این کد رو زدم ولی تست اول جواب YES میده...اشکال چیه؟
#include <iostream>
#include <vector>
using namespace std;
#define N 22

int n,m,p,mark[N*N];
string s;
vector <int> e[N*N];


void clr()
{
p=0;
for(int i=0;i<N*N;i++)
mark[i]=false;
}

void dfs(int x)
{
p++;
mark[x]=true;
for(int i=0;i<e[x].size();i++)
if(mark[e[x][i]]==false)
dfs(e[x][i]);
}

int main() {

cin>>n>>m;
cin>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='>')
for(int j=0;j<m-1;j++)
e[m*i+j].push_back(m*i+j+1);
else
for(int j=m-1;j>0;j--)
e[m*i+j].push_back(m*i+j-1);
}
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j]=='v')
for(int i=0;i<n-1;i++)
e[m*i+j].push_back(m*(i+1)+j);
else
for(int i=n-1;i>0;i--)
e[m*i+j].push_back(m*(i-1)+j);
}

for(int i=0;i<n*m;i++)
{
dfs(0);
if(p!=n*m)
{
cout<<"NO"<<endl;
return 0;
}
clr();
}
cout<<"YES"<<endl;
return 0;
}

نحوه کار کد هم اینه که از سوال یه گراف میسازه بعد dfs میزنه

[rahnema1]

سلام
یه اصلاح انجام دادم

#include <vector>
#include <iostream>
#include <string>
using namespace std;
struct Taghato
{
bool value;
Taghato* next[2];
Taghato () : value(false), next{nullptr, nullptr}{};
};
int dfs(Taghato* taghato, bool marked)
{
taghato->value = marked;
int sumNodes = 0;
for ( int i = 0; i < 2; i++)
{
if(taghato->next[i] != nullptr && taghato->next[i]->value != marked)
{
sumNodes += dfs(taghato->next[i], marked);
}
}
return sumNodes + 1;
}
int main()
{
int satr;
int sotoon;
string jahat;
cin >> satr >> sotoon;
vector<vector<Taghato> > shabake(satr, vector<Taghato>(sotoon));
cin >> jahat;
for ( int i = 0; i < satr; i++)
{
if (jahat[i] == '>')
{
for ( int j = 0; j < sotoon - 1; j++)
{
shabake[i][j].next[0] = &shabake[i][j + 1];
}
}
else
{
for ( int j = sotoon - 1; j > 0; j--)
{
shabake[i][j].next[0] = &shabake[i][j - 1];
}
}
}
cin >> jahat;
for ( int j = 0; j < sotoon; j++)
{
if (jahat[j] == 'v')
{
for ( int i = 0; i < satr - 1; i++)
{
shabake[i][j].next[1] = &shabake[i + 1][j];
}
}
else
{
for ( int i = satr - 1; i > 0; i--)
{
shabake[i][j].next[1] = &shabake[i - 1][j];
}
}
}
for ( int i = 0; i < satr; i++)
{
for ( int j = 0; j < sotoon; j++)
{
if (dfs(&shabake[i][j], !shabake[i][j].value) != satr * sotoon)
{
cout << "NO";
return 0;
}
}
}
cout << "YES";
return 0;
}

[sa1378]

سلام
یه اصلاح انجام دادم

#include <vector>
#include <iostream>
#include <string>
using namespace std;
struct Taghato
{
bool value;
Taghato* next[2];
Taghato () : value(false), next{nullptr, nullptr}{};
};
int dfs(Taghato* taghato, bool marked)
{
taghato->value = marked;
int sumNodes = 0;
for ( int i = 0; i < 2; i++)
{
if(taghato->next[i] != nullptr && taghato->next[i]->value != marked)
{
sumNodes += dfs(taghato->next[i], marked);
}
}
return sumNodes + 1;
}
int main()
{
int satr;
int sotoon;
string jahat;
cin >> satr >> sotoon;
vector<vector<Taghato> > shabake(satr, vector<Taghato>(sotoon));
cin >> jahat;
for ( int i = 0; i < satr; i++)
{
if (jahat[i] == '>')
{
for ( int j = 0; j < sotoon - 1; j++)
{
shabake[i][j].next[0] = &shabake[i][j + 1];
}
}
else
{
for ( int j = sotoon - 1; j > 0; j--)
{
shabake[i][j].next[0] = &shabake[i][j - 1];
}
}
}
cin >> jahat;
for ( int j = 0; j < sotoon; j++)
{
if (jahat[j] == 'v')
{
for ( int i = 0; i < satr - 1; i++)
{
shabake[i][j].next[1] = &shabake[i + 1][j];
}
}
else
{
for ( int i = satr - 1; i > 0; i--)
{
shabake[i][j].next[1] = &shabake[i - 1][j];
}
}
}
for ( int i = 0; i < satr; i++)
{
for ( int j = 0; j < sotoon; j++)
{
if (dfs(&shabake[i][j], !shabake[i][j].value) != satr * sotoon)
{
cout << "NO";
return 0;
}
}
}
cout << "YES";
return 0;
}

ممنون
قبل از اینکه کد رو بخونم میشه بگید الگوریتمش چه تغییراتی کرده؟
برای راحتی کارم :)
...
یه چیز دیگه هم هست...بدون پوینتر نمیشه نوشت؟

[rahnema1]

ممنون
قبل از اینکه کد رو بخونم میشه بگید الگوریتمش چه تغییراتی کرده؟
برای راحتی کارم :)
...
یه چیز دیگه هم هست...بدون پوینتر نمیشه نوشت؟

تقریبا واضحه اشاره گر ها مشخص می کنه بعد از تقاطع فعلی دو تقاطع بعدی کدام هستند
در dfs هم دیگه لازم نیست clear بشه. اگه سفید بود سیاه می کنیم. اگه سیاه بود سفید می کنیم
بدون اشاره گرهم میشه انجام داد ولی نه به این صورت که شما نوشتید. چون در درختی که شما درست کردید وقتی به یک برگ رسیدیم معلوم نیست برگ بعدی کدومه
فکر می کنم اشاره گر سر راست تر باشه