问题标题: 酷町堂题库1403数字方阵20分？

点击此处查看题目

1403   数字方阵

题目描述 Description

由数字组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。 现要求把闭合圈内的所有数字都填写成2.

输入描述 Input Description

每组测试数据第一行一个整数：n。其中n(1<=n<=8)
接下来n行，由0和1组成的n*n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。

输出描述 Output Description

变化后的闭合圈。

样例输入 Sample Input

例如：6X6的方阵（n=6），变化前和变化后的方阵如下：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

样例输出 Sample Output

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

数据范围及提示 Data Size & Hint

深度搜索 || 广度搜索

 

#include<iostream>
using namespace std;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,a[9][9];
int ans[40][2];
int x,y;
bool used[10][10];
int nextc,nextr;
bool canJump(int x,int y)
{
	if(x>=1&&x<=n&&y>=1&&y<=n&&a[x][y]&&!used[x][y]) return true;
	return false;
}
void search(int c,int r,int t)
{
	if(c==x&&r==y&&t!=1)
	{
		for(int i=1;i<t;i++)
		{
			for(int j=ans[i][0];j>=0;j++)
			{
				if(a[j+1][ans[i][1]]==0) a[j+1][ans[i][1]]=2;
				else break;
			}
		}
		return ;
	}
	if(t!=1) used[c][r]=true;
	for(int i=0;i<4;i++)
	{
		nextc=c+dir[i][0];
		nextr=r+dir[i][1];
		if(canJump(nextc,nextr))
		{
			ans[t][0]=nextc;
			ans[t][1]=nextr;
			search(nextc,nextr,t+1);
		}
	}
	used[c][r]=false;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j])
			{
				x=i;
				y=j;
				search(i,j,1);
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<' ';
		}
		cout<<endl;
	}
	return 0;
}

一共五个测试点，两个答案错，两个超时。

曾凡一在2018-01-26 11:57:13追加了内容

如何实现？