看了半天題目，原以為有什麼高深的方法，沒想到最後暴力加了個關鍵的剪枝就過了，囧，不過還是TLE了很多次。。。。。。
[cpp]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int mp[10][10];
int n , m , lim;
bool den[10][10];
bool valid(int x,int y)
{
return x>=1 && x<=n && y>=1 && y<=m;
}
bool check()
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mp[i][j] == -2)return false;
if(mp[i][j]>=1 && mp[i][j] <= 4) return false;
}
}
return true;
}
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
bool canput(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(valid(tx,ty))
{
if( mp[tx][ty] == 0 ) return false;
}
}
return true;
}
void go(int x,int y)
{
if(mp[x][y]==-2)
{
mp[x][y] = 5;
return ;
}
if(mp[x][y]>=5) mp[x][y]++;
}
void gao(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(valid(tx,ty))
{
if(mp[tx][ty]>=1 && mp[tx][ty]<=4) mp[tx][ty] --;
}
}
for(int i=y+1;i<=m;i++)
{
go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=y-1;i>=1;i--)
{
go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=x-1;i>=1;i--)
{
go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
for(int i=x+1;x<=n;i++)
{
go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
}
void Go(int x,int y)
{
if(mp[x][y]==5) mp[x][y] = -2;
if(mp[x][y]> 5) mp[x][y] -- ;
}
void clear(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(valid(tx,ty))
{
if(mp[tx][ty]>=0 && mp[tx][ty]<=3) mp[tx][ty] ++;
}
}
for(int i=y+1;i<=m;i++)
{
Go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=y-1;i>=1;i--)
{
Go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=x-1;i>=1;i--)
{
Go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
for(int i=x+1;x<=n;i++)
{
Go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
}
int ans;
void dfs(int dep,int x,int y)
{
if(dep>ans) return ;
if(x>n)
{
if(check())
{
if(dep<ans) ans=dep;
}
return ;
}
if(x>1 && mp[x-1][y]==-2 && mp[x][y]>=-1&&mp[x][y]<=4 ) return ;
if(y<m) dfs(dep,x,y+1);
else dfs(dep,x+1,1);
if(mp[x][y]==-2)
{
if(canput(x,y))
{
den[x][y] = true;
mp[x][y] = 5;
gao(x,y);
if(y<m) dfs(dep+1,x,y+1);
else dfs(dep+1,x+1,1);
den[x][y]=false;
mp[x][y] = -2;
clear(x,y);
}
}
}
int main()
{
int b , r , c , k ;
while(scanf("%d%d",&n,&m),n||m)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
mp[i][j] = - 2;
}
}
scanf("%d",&b);
for(int i = 0; i < b; i++)
{
scanf("%d%d%d",&r,&c,&k);
mp[r][c] = k;
}
ans = 1000;
dfs(0,1,1);
if(ans<1000) printf("%d\n",ans);
else puts("No solution");
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int mp[10][10];
int n , m , lim;
bool den[10][10];
bool valid(int x,int y)
{
return x>=1 && x<=n && y>=1 && y<=m;
}
bool check()
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mp[i][j] == -2)return false;
if(mp[i][j]>=1 && mp[i][j] <= 4) return false;
}
}
return true;
}
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
bool canput(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(valid(tx,ty))
{
if( mp[tx][ty] == 0 ) return false;
}
}
return true;
}
void go(int x,int y)
{
if(mp[x][y]==-2)
{
mp[x][y] = 5;
return ;
}
if(mp[x][y]>=5) mp[x][y]++;
}
void gao(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(valid(tx,ty))
{
if(mp[tx][ty]>=1 && mp[tx][ty]<=4) mp[tx][ty] --;
}
}
for(int i=y+1;i<=m;i++)
{
go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=y-1;i>=1;i--)
{
go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=x-1;i>=1;i--)
{
go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
for(int i=x+1;x<=n;i++)
{
go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
}
void Go(int x,int y)
{
if(mp[x][y]==5) mp[x][y] = -2;
if(mp[x][y]> 5) mp[x][y] -- ;
}
void clear(int x,int y)
{
for(int i = 0; i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(valid(tx,ty))
{
if(mp[tx][ty]>=0 && mp[tx][ty]<=3) mp[tx][ty] ++;
}
}
for(int i=y+1;i<=m;i++)
{
Go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=y-1;i>=1;i--)
{
Go(x,i);
if(mp[x][i]>=-1 && mp[x][i] <= 4) break;
}
for(int i=x-1;i>=1;i--)
{
Go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
for(int i=x+1;x<=n;i++)
{
Go(i,y);
if(mp[i][y]>=-1 && mp[i][y] <= 4) break;
}
}
int ans;
void dfs(int dep,int x,int y)
{
if(dep>ans) return ;
if(x>n)
{
if(check())
{
if(dep<ans) ans=dep;
}
return ;
}
if(x>1 && mp[x-1][y]==-2 && mp[x][y]>=-1&&mp[x][y]<=4 ) return ;
if(y<m) dfs(dep,x,y+1);
else dfs(dep,x+1,1);
if(mp[x][y]==-2)
{
if(canput(x,y))
{
den[x][y] = true;
mp[x][y] = 5;
gao(x,y);
if(y<m) dfs(dep+1,x,y+1);
else dfs(dep+1,x+1,1);
den[x][y]=false;
mp[x][y] = -2;
clear(x,y);
}
}
}
int main()
{
int b , r , c , k ;
while(scanf("%d%d",&n,&m),n||m)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
mp[i][j] = - 2;
}
}
scanf("%d",&b);
for(int i = 0; i < b; i++)
{
scanf("%d%d%d",&r,&c,&k);
mp[r][c] = k;
}
ans = 1000;
dfs(0,1,1);
if(ans<1000) printf("%d\n",ans);
else puts("No solution");
}
return 0;
}
