#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
int n,m;
bool sus[105][105],st[105][105];
int sel[105][105];
bool loop = false;
int nr = 0;
int cnt = 0;
vector<pair<int,int>> c;
int p[105];
void Fill(int i, int j, int si, int sj)
{
++nr;
sel[i][j] = cnt;
if(!sus[i][j] && i-1>0)
{
if(sel[i-1][j])
{
if(sel[i-1][j]==cnt && (i-1!=si || j!=sj))
{
loop = true;
}
}
else
{
Fill(i-1,j,i,j);
}
}
if(!sus[i+1][j] && i+1<=n)
{
if(sel[i+1][j])
{
if(sel[i+1][j]==cnt && (i+1!=si || j!=sj))
{
loop = true;
}
}
else
{
Fill(i+1,j,i,j);
}
}
if(!st[i][j] && j-1>0)
{
if(sel[i][j-1])
{
if(sel[i][j-1]==cnt && (i!=si || j-1!=sj))
{
loop = true;
}
}
else
{
Fill(i,j-1,i,j);
}
}
if(!st[i][j+1] && j+1<=m)
{
if(sel[i][j+1])
{
if(sel[i][j+1]==cnt && (i!=si || j+1!=sj))
{
loop = true;
}
return;
}
else
{
Fill(i,j+1,i,j);
}
}
}
int Back(int k, bool turn, int last)
{
bool done1 = false, done2 = false;
if(turn==1)
{
int Max = -oo;
for(int i=0;i<c.size();i++)
{
if(i>0 && c[i]==c[i-1])
{
continue;
}
if(c[i].second==true)
{
if(p[i]==0 && last)
{
p[i] = 1;
Max = max(Max,Back(k+1,0,0));
p[i] = 0;
}
else if(p[i]==1)
{
p[i] = 3;
Max = max(Max,Back(k+1,1,1)+c[i].first);
p[i] = 1;
if(c[i].first>4)
{
p[i] = 2;
Max = max(Max,Back(k+1,0,1)+c[i].first-4);
p[i] = 1;
}
}
else if(p[i]==2 && !done2)
{
done2 = true;
p[i] = 3;
Max = max(Max,Back(k+1,1,1)+4);
p[i] = 2;
}
}
else
{
if(p[i]==0 && last)
{
p[i] = 1;
Max = max(Max,Back(k+1,0,0));
p[i] = 0;
}
else if(p[i]==1)
{
p[i] = 3;
Max = max(Max,Back(k+1,1,1)+c[i].first);
p[i] = 1;
if(c[i].first>2)
{
p[i] = 2;
Max = max(Max,Back(k+1,0,1)+c[i].first-2);
p[i] = 1;
}
}
else if(p[i]==2 && !done1)
{
done1 = true;
p[i] = 3;
Max = max(Max,Back(k+1,1,1)+2);
p[i] = 2;
}
}
}
if(Max==-oo)
{
Max = 0;
}
return Max;
}
else
{
int Min = oo;
for(int i=0;i<c.size();i++)
{
if(i>0 && c[i]==c[i-1])
{
continue;
}
if(c[i].second==true)
{
if(p[i]==0 && last)
{
p[i] = 1;
Min = min(Min,Back(k+1,1,0));
p[i] = 0;
}
else if(p[i]==1)
{
p[i] = 3;
Min = min(Min,Back(k+1,0,1)-c[i].first);
p[i] = 1;
if(c[i].first>4)
{
p[i] = 2;
Min = min(Min,Back(k+1,1,1)-(c[i].first-4));
p[i] = 1;
}
}
else if(p[i]==2 && !done2)
{
done2 = true;
p[i] = 3;
Min = min(Min,Back(k+1,0,1)-4);
p[i] = 2;
}
}
else
{
if(p[i]==0 && last)
{
p[i] = 1;
Min = min(Min,Back(k+1,1,0));
p[i] = 0;
}
else if(p[i]==1)
{
p[i] = 3;
Min = min(Min,Back(k+1,0,1)-c[i].first);
p[i] = 1;
if(c[i].first>2)
{
p[i] = 2;
Min = min(Min,Back(k+1,1,1)-(c[i].first-2));
p[i] = 1;
}
}
else if(p[i]==2 && !done1)
{
done1 = true;
p[i] = 3;
Min = min(Min,Back(k+1,0,1)-2);
p[i] = 2;
}
}
}
if(Min==oo)
{
Min = 0;
}
return Min;
}
}
void debug(vector<pair<int,int>> v)
{
for(auto it : v)
{
cerr<<it.first<<' '<<it.second<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1; i<=n+1; i++)
{
for(int j=1; j<=m; j++)
{
char ch;
cin>>ch;
sus[i][j] = ch-'0';
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m+1; j++)
{
char ch;
cin>>ch;
st[i][j] = ch-'0';
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(sus[i][j] && sus[i+1][j] && st[i][j] && st[i][j+1])
{
sel[i][j] = -1;
continue;
}
if(sel[i][j])
{
continue;
}
nr = 0;
++cnt;
loop = false;
Fill(i,j,0,0);
c.push_back({nr,loop});
}
}
sort(c.begin(),c.end());
cout<<Back(1,1,-1)<<'\n';
return 0;
}
Compilation message
game.cpp: In function 'int Back(int, bool, int)':
game.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i=0;i<c.size();i++)
| ~^~~~~~~~~
game.cpp:153:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int i=0;i<c.size();i++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
