#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using tpii=pair<int,pair<int,int>>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;
int main(){
_3qplfh5;
int h,w;
cin>>h>>w;
vec(vi) a(h,vi(w));
rep(i,h){
string s;
cin>>s;
rep(j,w){
a[i][j]=(s[j]=='1');
}
}
vi rbts;
rep(i,h){
rep(j,w){
if(a[i][j]){
rbts.pb(i*w+j);
}
}
}
int n=sz(rbts);
assert(n<15);
int mi=1e9;
vec(tpii) pans;
rep(msk,(1<<n)){
vec(vi) nea;
nea=a;
int now=0;
vec(tpii) nevc;
rep(i,n){
int x=rbts[i]/w,y=rbts[i]%w;
bool pok=0;
if(msk&(1<<i)){
while(x+1<h){
x++;
if(nea[x][y]) break;
pok=1;
now++;
nea[x][y]=1;
}
}else{
while(y+1<w){
y++;
if(nea[x][y]) break;
pok=1;
now++;
nea[x][y]=1;
}
}
if(pok){
nevc.pb({msk&(1<<i),{x,y}});
}
}
bool gok=1;
rep(i,h){
rep(j,w)if(!nea[i][j])gok=0;
}
if(now<mi and gok){
mi=now;
pans=nevc;
}
}
cout<<sz(pans)<<"\n";
for(auto p : pans){
cout<<p.se.fi+1<<" "<<p.se.se+1<<" ";
if(p.fi==0){
cout<<"DESNO\n";
}else{
cout<<"DOLJE\n";
}
}
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
204 KB |
First line is correct, but the reconstruction is not properly formatted. |
| 2 |
Incorrect |
0 ms |
204 KB |
First line is not correct. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
424 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
204 KB |
First line is correct, but the reconstruction is not properly formatted. |
| 2 |
Incorrect |
0 ms |
204 KB |
First line is not correct. |
| 3 |
Halted |
0 ms |
0 KB |
- |
