解题思路
dfs+剪枝
过29个点
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
const int N=10;
typedef pair<int,int> PII;
int dx[9] = {-1, -1, -1, 0, 1, 1, 1, 0,0};
int dy[9] = {-1, 0, 1, 1, 1, 0, -1, -1,0};
vector<PII> seq;
char g[N][N];
int d[N][N];
int n,m;
int cnt_all;
void printT()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d",d[i][j]);
printf("\n");
}
}
bool check(int a)
{
for(auto t:seq)
{
int x=t.x,y=t.y;
if(x>a)
continue;
int num=g[x][y]-'0';
int cnt=0;
for(int i=0;i<9;i++)
{
int xx=t.x+dx[i],yy=t.y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=m)
continue;
if(d[xx][yy]==1)
cnt++;
}
if(cnt!=num)
{
return false;
}
}
return true;
}
bool dfs(int u,int sum)
{
if(u==n*m)
{
int x=u/n;
if(check(x))
{
printT();
return true;
}
return false;
}
int x=u/m,y=u-x*m;
// cout<<x<<"-"<<y<<endl;
if(sum>cnt_all) //优化1,约束条件优化
return false;
if(!y&&x-2>=0) //优化2,一边枚举一边检查行
{
if(!check(x-2))
return false;
}
for(int i=1;i>=0;i--) //优化3,枚举顺序优化
{
if(!i)
{
if(dfs(u+1,sum))
return true;
}
else
{
d[x][y]=1;
if(dfs(u+1,sum+1))
return true;
d[x][y]=0;
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
scanf("%s",g[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(g[i][j]>='0'&&g[i][j]<='9')
{
cnt_all+=g[i][j]-'0';
seq.push_back({i,j});
}
}
dfs(0,0);
return 0;
}
AC 更加精细的剪枝-加入检查(x-1,y-2)点的优化
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
const int N=10;
typedef pair<int,int> PII;
int dx[9] = {-1, -1, -1, 0, 1, 1, 1, 0,0};
int dy[9] = {-1, 0, 1, 1, 1, 0, -1, -1,0};
vector<PII> seq;
char g[N][N];
int d[N][N];
int n,m;
int cnt_all;
void printT()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d",d[i][j]);
printf("\n");
}
}
bool check_point(int a,int b)
{
for(auto t:seq)
{
if(t.x==a&&t.y==b)
{
int cnt=0;
for(int i=0;i<9;i++)
{
int xx=t.x+dx[i],yy=t.y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=m)
continue;
if(d[xx][yy])
cnt++;
}
if(cnt!=g[t.x][t.y]-'0')
return false;
else
return true;
}
}
return true;
}
bool check(int a)
{
for(auto t:seq)
{
int x=t.x,y=t.y;
if(x>a)
continue;
int num=g[x][y]-'0';
int cnt=0;
for(int i=0;i<9;i++)
{
int xx=t.x+dx[i],yy=t.y+dy[i];
if(xx<0||xx>=n||yy<0||yy>=m)
continue;
if(d[xx][yy]==1)
cnt++;
}
if(cnt!=num)
{
return false;
}
}
return true;
}
bool dfs(int u,int sum)
{
if(u==n*m)
{
int x=u/n;
if(check(x))
{
printT();
return true;
}
return false;
}
int x=u/m,y=u-x*m;
// cout<<x<<"-"<<y<<endl;
if(sum>cnt_all)
return false;
if(!y&&x-2>=0)
{
if(!check(x-2))
return false;
}
if(x>=1&&y>=2)
if(!check_point(x-1,y-2))
return false;
for(int i=1;i>=0;i--)
{
if(!i)
{
if(dfs(u+1,sum))
return true;
}
else
{
d[x][y]=1;
if(dfs(u+1,sum+1))
return true;
d[x][y]=0;
}
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
scanf("%s",g[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(g[i][j]>='0'&&g[i][j]<='9')
{
cnt_all+=g[i][j]-'0';
seq.push_back({i,j});
}
}
dfs(0,0);
return 0;
}