ACM 838 Q838: Worm World (未完成版)
作法 : 完全的暴搜 得到TLE
/************************************************************/
#include<stdio.h>
#include<stdlib.h>
int map[13][13]={0},max=0;
int used[1001]={0},t,n,record[13][13]={0};
void DFS (int x,int y,int L)
{
if(L>max) max=L;
if(x+1<=n&&used[map[x+1][y]]==0)
{
used[map[x+1][y]]=1;
DFS (x+1,y,L+1);
used[map[x+1][y]]=0;
}
if(x-1>=1&&used[map[x-1][y]]==0)
{
used[map[x-1][y]]=1;
DFS (x-1,y,L+1);
used[map[x-1][y]]=0;
}
if(y+1<=n&&used[map[x][y+1]]==0)
{
used[map[x][y+1]]=1;
DFS (x,y+1,L+1);
used[map[x][y+1]]=0;
}
if(y-1>=1&&used[map[x][y-1]]==0)
{
used[map[x][y-1]]=1;
DFS (x,y-1,L+1);
used[map[x][y-1]]=0;
}
}
main()
{
while(scanf("%d",&t)==1)
while(t--)
{
scanf("%d",&n);
int a,b,c;
for(a=1;a<=n;a++)
for(b=1;b<=n;b++)
{
scanf("%d",&map[a][b]);
record[a][b]=0;
}
int last=0;
for(a=1;a<=n;a++)
for(b=1;b<=n;b++)
{
used[map[a][b]]=1;
max=0;
DFS(a,b,1);
if(max>last) last=max;
record[a][b]=max;
used[map[a][b]]=0;
}
printf("%d\n",last);
if(t!=1) printf("\n");
}
return 0;
}
/*
2
3
1 2 1
2 3 4
3 2 1
8
6 8 18 15 24 20 2 20
6 2 15 2 17 15 3 7
0 11 18 16 20 15 1 11
6 2 6 13 4 17 20 16
5 12 7 2 3 5 18 23
7 13 3 2 2 11 4 23
16 23 10 2 4 12 5 20
17 12 10 1 13 12 6 20
*/