发现数据范围极小，可以直接打表。

#include<bits/stdc++.h>
using namespace std;
int n,m,c;
int a[15][15];
void dfs(int x,int y){
	if(x==n+1){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<a[i][j]<<",";
			}cout<<endl;
		}
		exit(0);
	}
	int nx=x,ny=y+1;if(ny>m)ny=1,nx++;
	int r=rand();
	for(int i=r;i<=c+r;i++){//尝试填颜色 i%c+1
		bool f=1;
		for(int j=1;j<x;j++){
			for(int k=1;k<y;k++){
				if(a[j][k]==a[j][y]&&a[j][y]==a[x][k]&&a[x][k]==i%c+1)f=0;
			}
		}
		if(f){
			a[x][y]=i%c+1;
			dfs(nx,ny);
			a[x][y]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	srand(time(0));
	cin>>n>>m>>c;
	dfs(1,1);
	return 0;
}

其中使用随机数的原因是，这样不会让程序开始尝试填一堆 $1$，导致后面经常出现无解需要回溯的情况。

输入 8 9 3（输入再大点等待的就不知道多久了），运气好的话，等待几秒，就会出来一份答案：

2,1,1,3,3,3,2,2,2,
3,1,2,3,1,1,1,1,3,
1,3,1,2,2,1,3,2,3,
2,2,1,3,1,2,3,3,1,
1,2,3,2,1,3,2,3,3,
3,2,3,1,3,1,3,2,1,
1,2,2,1,2,3,3,1,2,
1,3,2,2,3,2,1,3,1,

由此可以得到：

int b[15][15]={
	{0},
	{0, 2,1,1,3,3,3,2,2,2,0},
	{0, 3,1,2,3,1,1,1,1,3,0},
	{0, 1,3,1,2,2,1,3,2,3,0},
	{0, 2,2,1,3,1,2,3,3,1,0},
	{0, 1,2,3,2,1,3,2,3,3,0},
	{0, 3,2,3,1,3,1,3,2,1,0},
	{0, 1,2,2,1,2,3,3,1,2,0},
	{0, 1,3,2,2,3,2,1,3,1,0},
	{0, 0,0,0,0,0,0,0,0,0,0},
	{0, 0,0,0,0,0,0,0,0,0,0},
};

再进行小小的填空和手动微调：

int b[15][15]={
	{0},
	{0, 2,1,3,3,1,3,2,1,2,1},
	{0, 2,2,2,1,1,1,1,3,3,3},
	{0, 1,3,2,1,2,3,2,1,1,3},
	{0, 2,3,1,3,3,2,1,1,3,2},
	{0, 2,1,3,2,3,1,3,2,1,3},
	{0, 3,2,1,3,1,2,2,2,1,3},
	{0, 1,2,1,3,2,1,3,3,2,1},
	{0, 1,1,2,2,3,3,1,3,2,2},
	{0, 3,1,1,1,2,3,3,2,3,2},
	{0, 3,3,3,2,2,2,1,3,1,1},
};

再放到原来的代码中：

#include<bits/stdc++.h>
using namespace std;
int n,m,c;
int a[15][15];
int b[15][15]={
	{0},
	{0, 2,1,3,3,1,3,2,1,2,1},
	{0, 2,2,2,1,1,1,1,3,3,3},
	{0, 1,3,2,1,2,3,2,1,1,3},
	{0, 2,3,1,3,3,2,1,1,3,2},
	{0, 2,1,3,2,3,1,3,2,1,3},
	{0, 3,2,1,3,1,2,2,2,1,3},
	{0, 1,2,1,3,2,1,3,3,2,1},
	{0, 1,1,2,2,3,3,1,3,2,2},
	{0, 3,1,1,1,2,3,3,2,3,2},
	{0, 3,3,3,2,2,2,1,3,1,1},
};
void dfs(int x,int y){
	if(x==n+1){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<a[i][j]<<" ";
			}cout<<endl;
		}
		exit(0);
	}
	int nx=x,ny=y+1;if(ny>m)ny=1,nx++;
	for(int i=1;i<=c;i++){//尝试填颜色 i
		bool f=1;
		for(int j=1;j<x;j++){
			for(int k=1;k<y;k++){
				if(a[j][k]==a[j][y]&&a[j][y]==a[x][k]&&a[x][k]==i)f=0;
			}
		}
		if(f){
			a[x][y]=i;
			dfs(nx,ny);
			a[x][y]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>c;
	if(c==2)dfs(1,1);
	else{
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<b[i][j]<<" ";
			}cout<<endl;
		}
	}
	return 0;
}

轻松 AC。