HDU 5386 Cover(求一个初始状态数图到另一个终止状态数图所需的步骤)

时间:2021-06-21 03:01:35

题目地址:点击打开链接

思路:暴力模拟每种步骤到最后判断,其实没有必要,因为从初始到终止肯定有一种步骤,从终止到初始回溯就行,给图赋值的时候要从1开始循环,因为步骤里面图的行数和列数都是从1开始搞的

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int map1[110][110],map2[110][110];
char a[510][2];
int b[510],c[510],down[510],visit[510],n,m,flag;

void back_sort(int cur)
{
int i,j;
if(flag)
return;
if(cur == m)
{
printf("%d",down[m-1]);
for(i=m-2; i>=0; i--)
{
printf(" %d",down[i]);
}
printf("\n");
flag = 1;
return;
}
for(i=0; i<m; i++)
{
if(!visit[i])
{
if(a[i][0] == 'L')
{
for(j=1; j<=n; j++)
{
if(map2[j][b[i]] && map2[j][b[i]] != c[i])//看列是否相同
break;
}
if(j > n)
{
for(j=1; j<=n; j++)
{
map2[j][b[i]] = 0;
}
visit[i] = 1;
down[cur] = i + 1;
back_sort(cur+1);
visit[i] = 0;
}
}
else
{
for(j=1; j<=n; j++)
{
if(map2[b[i]][j] && map2[b[i]][j] != c[i])//看行是否相同
break;
}
if(j > n)
{
for(j=1; j<=n; j++)
{
map2[b[i]][j] = 0;
}
visit[i] = 1;
down[cur] = i + 1;
back_sort(cur+1);
visit[i] = 0;
}
}
}
}
}

int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
flag = 0;
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d",&map1[i][j]);
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d",&map2[i][j]);
}
}
memset(visit,0,sizeof(visit));
scanf("%d",&m);
for(i=0; i<m; i++)
{
scanf("%s%d%d",a[i],&b[i],&c[i]);
}
back_sort(0);
}
return 0;
}