本题的难点在于如何处理大于小于关系。 我选择用一个数组存储(x,y)点对应的所有限制关系。
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=10;
int juzhen[N][N]={{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9}};
char g[2*N][2*N];
int res[N][N];
bool sthang[N][N],stlie[N][N],stgrid[N][N];
struct cmp_info{
int x,y;
bool greater;
};
vector<cmp_info> info[N][N];
int row_xuhao[6]={2,3,5,6,8,9};
bool solved=0;
void input_row(int j)
{
for(int k=0;k<6;k++)
{
bool flag;
char input[3];
scanf("%s",&input);
if(input[0]=='>') flag=0;
else flag=1;
info[j][row_xuhao[k]].push_back({j,row_xuhao[k]-1,flag});
}
}
void input_col(int j)
{
for(int k=1;k<=9;k++)
{
bool flag;
char input[3];
scanf("%s",&input);
if(input[0]=='v') flag=0;
else flag=1;
info[j+1][k].push_back({j,k,flag});
}
}
bool compare(int x,int y,int val)
{
for(auto it:info[x][y])
{
if(val>res[it.x][it.y]!=it.greater) return false;
}
return true;
}
void dfs(int x,int y)
{
if(solved) return;
for(int i=1;i<=9;i++)
{
if(sthang[x][i]||stlie[y][i]||stgrid[juzhen[x][y]][i]) continue;
if(!compare(x,y,i)) continue;
res[x][y]=i;
sthang[x][i]=1;
stlie[y][i]=1;
stgrid[juzhen[x][y]][i]=1;
if(x==9&&y==9)
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++) cout<<res[i][j]<<" ";
cout<<endl;
}
solved=1;
}
else if(y==9) dfs(x+1,1);
else dfs(x,y+1);
res[x][y]=0;
sthang[x][i]=0;
stlie[y][i]=0;
stgrid[juzhen[x][y]][i]=0;
}
}
int main()
{
for(int i=0;i<3;i++)
{
for (int j = 1; j < 3; ++j)
input_row(i * 3 + j), input_col(i * 3 + j);
input_row((i + 1) * 3);
}
dfs(1,1);
}