这个题目说两种思路
第一种：也是比较多人采用的，一个个格子顺序搜素，放灯不放灯两种状态，加一个剪枝，如果当前点为墙，且其上面为黑暗的地方，剪枝。思路非常清晰。
第二种：也是本菜采用的，效果很差，先找有限制的障碍点，其周围挨个放灯，每次从头到尾扫描找这样的点。
如果没有这样的点，随便找一个黑暗的点，其x，y轴上必然还要放一个灯，枚举这些点放灯。400+ms飘过。。。
#include
#include
#include
using namespace std;
const int maxn=7,inf=9999999;
int timee;
int n,m;
char a[10][10];
int check(int x,int y)
{
if(a[x][y]<=4) return(0);
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
if(i==0||j==0)
if(i||j)
if(x+i>=1&&x+i<=n)
if(y+j>=1&&y+j<=m)
{
if(a[x+i][y+j]==0)
return(0);
}
for(int j=y;j>=1;j--)
{
if(a[x][j]>=-1&&a[x][j]<=4) break;
else if(a[x][j]==-2) return(0);
}
for(int j=y;j<=m;j++)
{
if(a[x][j]>=-1&&a[x][j]<=4) break;
else if(a[x][j]==-2) return(0);
}
for(int i=x;i>=1;i--)
{
if(a[i][y]>=-1&&a[i][y]<=4) break;
else if(a[i][y]==-2) return(0);
}
for(int i=x;i<=n;i++)
{
if(a[i][y]>=-1&&a[i][y]<=4) break;
else if(a[i][y]==-2) return(0);
}
return(1);
}
int work(int x,int y,int tmp)
{
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
if(i==0||j==0)
if(i||j)
if(x+i>=1&&x+i<=n)
if(y+j>=1&&y+j<=m)
if(a[x+i][y+j]>=0&&a[x+i][y+j]<=4)
{
// printf("%d %d\n",x+i,y+j);
a[x+i][y+j]-=tmp;
}
for(int j=y-1;j>=1;j--)
{
if(a[x][j]>=-1&&a[x][j]<=4) break;
a[x][j]+=tmp;
}
for(int j=y+1;j<=m;j++)
{
if(a[x][j]>=-1&&a[x][j]<=4) break;
a[x][j]+=tmp;
}
for(int i=x-1;i>=1;i--)
{
if(a[i][y]>=-1&&a[i][y]<=4) break;
a[i][y]+=tmp;
}
for(int i=x+1;i<=n;i++)
{
if(a[i][y]>=-1&&a[i][y]<=4) break;
a[i][y]+=tmp;
}
return(0);
}
int ans;
int dfs(int timm)
{
timee++;
if(timm>=ans) return(0);
int ture=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==5)
ture=0;
else if(a[i][j]>=1&&a[i][j]<=4)
ture=0;
if(ture)
{
ans=min(ans,timm);
return(0);
}
int x=0,y=0,tmp=5;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]<=4&&a[i][j]>=1)
{
if(a[i][j]
{
x=i;
y=j;
tmp=a[i][j];
}
}
if(x&&y)
{
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
if(x+i>=1&&x+i<=n)
if(y+j>=1&&y+j<=m)
if(i==0||j==0)
if(i||j)
{
if(check(x+i,y+j))
{
int ted=a[x+i][y+j];
a[x+i][y+j]=-2;
work(x+i,y+j,1);
dfs(timm+1);
work(x+i,y+j,-1);
a[x+i][y+j]=ted;
}
}
}
else
{
int x,y;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==5)
{
x=i;
y=j;
}
for(int i=x,j=y;j<=m;j++)
{
if(a[i][j]==-2) break;
if(a[i][j]>=-1&&a[i][j]<=4) break;
if(check(i,j))
{
int ted=a[i][j];
a[i][j]=-2;
work(i,j,1);
dfs(timm+1);
work(i,j,-1);
a[i][j]=ted;
}
}
for(int i=x,j=y-1;j>=1;j--)
{
if(a[i][j]==-2) break;
if(a[i][j]>=-1&&a[i][j]<=4) break;
if(check(i,j))
{
int ted=a[i][j];
a[i][j]=-2;
work(i,j,1);
dfs(timm+1);
work(i,j,-1);
a[i][j]=ted;
}
}
for(int i=x+1,j=y;i<=n;i++)
{
if(a[i][j]==-2) break;
if(a[i][j]>=-1&&a[i][j]<=4) break;
if(check(i,j))
{
int ted=a[i][j];
a[i][j]=-2;
work(i,j,1);
dfs(timm+1);
work(i,j,-1);
a[i][j]=ted;
}
}
for(int i=x-1,j=y;i>=1;i--)
{
if(a[i][j]==-2) break;
if(a[i][j]>=-1&&a[i][j]<=4) break;
if(check(i,j))
{
int ted=a[i][j];
a[i][j]=-2;
work(i,j,1);
dfs(timm+1);
work(i,j,-1);
a[i][j]=ted;
}
}
}
return(0);
}
int main()
{
while(scanf("%d %d",&n,&m),n&&m)
{
timee=0;
int k;
scanf("%d",&k);
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
a[i][j]=5;
for(int i=1;i<=k;i++)
{
int x,y,tmp;
scanf("%d %d %d",&x,&y,&tmp);
a[x][y]=tmp;
}
ans=inf;
dfs(0);
if(ans!=inf)
printf("%d\n",ans);
else
printf("No solution\n");
}
return 0;
}