smart robot
题意
冰封的梦想是成为一个法律大师。于是他造了一个聪明的机器人来帮助他。
机器人在N*N矩阵上
工作。矩阵中的所有数字都是小于 10 的非负整数。机器人可以在矩阵中移动。如果它处于矩阵的 （x，y） 位置，它可以移动到 （x+1，y） 、（x，y+1）、（x-1，y）、（x，y-1），这是机器人的相邻位置。但是机器人必须在矩阵内操作。它不能脱离矩阵。
机器人可以从矩阵中的任何位置开始，采取任何步骤，并且可以在矩阵中的任何位置
停止。我们连接机器人路径中的数字，以便获得一个神奇的数字。例如，如果机器人走3步，通过矩阵的3个数字，0，7和8，魔法数字是78。所有的魔法数字都是非负整数，机器人生成的数字不包含前0。
通过机器人，冰封了很多神奇
的数字。现在他想知道他拿不到的最小魔法数字是什么。
输入描述:
The first line is an integer N, denoting the length and width of the matrix.
The next N lines, N numbers per line, separated by spaces, represent this matrix. Ensure that each number in the matrix is less than 10 and greater than or equal to zero.
The numbers in the matrix are randomly generated.
1 \leq N \leq 501≤N≤50
输出描述:
One integer per line, indicating the smallest magic number that icebound can not get.
示例1
输入
4
1 2 3 4
3 6 7 8
0 1 5 4
9 1 1 1
输出
17
代码1：
(我看别人写的，不知道为什么计算到四位数就可以）
#include "stdio.h"
#include "string.h"
#define ll long long
int a[54][54];
int b[999999];
int n;
int tt[4][2]={0,1,1,0,0,-1,-1,0};
void ppp(int x,int y,int s,int step)
{
b[s]=1;
if(step==4)
return ;
for(int i=0;i<4;i++)
{
int tx=x+tt[i][0];
int ty=y+tt[i][1];
if(tx<1||ty<1||ty>n||tx>n)
continue;
ppp(tx,ty,s*10+a[tx][ty],step+1);
}
}
int main()
{
int i,m,k,l,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
ppp(i,j,a[i][j],1);
}
for(i=0;;i++)
if(!b[i])
break;
printf("%d\n",i);
}
代码2
自己理解的：先算一位数，没找到的话，再算两位数，没找到的话，再算三位数……
#include "stdio.h"
#include "queue"
#include "algorithm"
#include "math.h"
using namespace std;
struct pp
{
int x,y,s,k;
}t,h;
int tt[4][2]={0,1,1,0,0,-1,-1,0};
int n,m;
queue<pp>q;
int a[999][999];
int b[99999];
void ppp(int step)
{
int i,j;
while(!q.empty())
{
h=q.front();
if(h.k==step)
{
return;
}
q.pop();
for(i=0;i<4;i++)
{
t.x=h.x+tt[i][0];
t.y=h.y+tt[i][1];
t.k=h.k+1;
if(t.x<1||t.y<1||t.x>n||t.y>n)
continue;
t.s=h.s*10+a[t.x][t.y];
b[t.s]=1;
q.push(t);
}
}
}
int main()
{
int i,j,k,l;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
t.x=i,t.y=j,t.s=a[i][j];
t.k=1;
q.push(t);
b[a[i][j]]=1;
}
}
for(i=0;i<10;i++)
{
if(!b[i])
{
printf("%d\n",i);
return 0;
}
}
while(1)
{
for(i=2;;i++)
{
ppp(i);
int k1=pow(10,i-1),k2=pow(10,i);
for(j=k1;j<k2;j++)
{
if(!b[j])
{
printf("%d\n",j);
return 0;
}
}
}
}
}