const
s:array[1..4]of integer=(1,-1,0,0);
t:array[1..4]of integer=(0,0,1,-1);
type
treenode=record
x,y:longint;
end;
var
i,j,k,n,m,top,rear,x1,y1,x2,y2,xx,yy:longint;
ch:char;
map,dis:array[1..2000,1..2000]of longint;
q:array[1..4000000]of treenode;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(map[i,j]);
dis[i,j]:=-1;
end;
readln;
end;
readln(x1,y1);
readln(x2,y2);
top:=0;
rear:=1;
q[1].x:=x1;
q[1].y:=y1;
dis[x1,y1]:=0;
while top<rear do
begin
inc(top);
for i:=1 to 4 do
begin
xx:=s[i]+q[top].x;
yy:=t[i]+q[top].y;
if (xx>0)and(xx<=m)and(yy>0)and(yy<=n)and(dis[xx,yy]=-1)
and(map[xx,yy]=0)
then
begin
dis[xx,yy]:=dis[q[top].x,q[top].y]+1;
inc(rear);
q[rear].x:=xx;
q[rear].y:=yy;
end;
if (xx=x2)and(yy=y2)
then break;
end;
end;
if dis[x2,y2]=-1
then writeln('No Answer!')
else writeln(dis[x2,y2]);
end.
状态: Unaccepted
测评机： Xeond[6]
得分： 90分
提交日期： 2010-11-14 11:41:00
有效耗时： 1438毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时156ms
测试结果3: 通过本测试点|有效耗时157ms
测试结果4: 输出过长|用户输出数据超过标准输出两倍[标准输出1位|选手输出10位]
测试结果5: 通过本测试点|有效耗时156ms
测试结果6: 通过本测试点|有效耗时157ms
测试结果7: 通过本测试点|有效耗时156ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时156ms
测试结果10: 通过本测试点|有效耗时156ms
#include<stdio.h>//DFS深搜+最优性剪枝
#include<stdlib.h>
int max=100;
int a[2000][2000]={0},n,m;
int beginx,beginy,endx,endy;
int floodfill(int x,int y);
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
a[i][j]*=-1;//放便后面的数步子
}
scanf("%d%d%d%d",&beginx,&beginy,&endx,&endy);
beginx--;
beginy--;
endx--;
endy--;
a[beginx][beginy]++;
floodfill(beginx,beginy);//不用记录步子了，直接染色即可
max--;
if(max==99) printf("No Answer!");
else printf("%d",max);
system("pause");
return 0;
}
int floodfill(int x,int y)//-1为不可到达的点
{
if(a[x][y]>=max) return 0;
if(x==endx&&y==endy&&a[x][y]<max) {max=a[x][y];return 0;}
//上
if(x-1>=0&&a[x-1][y]!=-1)//等下测试是否会存在数组越界的情况，不知道&&先算哪边
{
if(a[x-1][y]==0) {a[x-1][y]=a[x][y]+1;floodfill(x-1,y);}
else
{
if(a[x-1][y]<=a[x][y]+1);
else {a[x-1][y]=a[x][y]+1;floodfill(x-1,y);}
}
}
//下
if(x+1<n&&a[x+1][y]!=-1)
{
if(a[x+1][y]==0) {a[x+1][y]=a[x][y]+1;floodfill(x+1,y);}
else
{
if(a[x+1][y]<=a[x][y]+1);
else {a[x+1][y]=a[x][y]+1;floodfill(x+1,y);}
}
}
//左
if(y-1>=0&&a[x][y-1]!=-1)
{
if(a[x][y-1]==0) {a[x][y-1]=a[x][y]+1;floodfill(x,y-1);}
else
{
if(a[x][y-1]<=a[x][y]+1);
else {a[x][y-1]=a[x][y]+1;floodfill(x,y-1);}
}
}
//右 if(y+1<m&&a[x][y+1]!=-1)
{
if(a[x][y+1]==0) {a[x][y+1]=a[x][y]+1;floodfill(x,y+1);}
else
{
if(a[x][y+1]<=a[x][y]+1);
else {a[x][y+1]=a[x][y]+1;floodfill(x,y+1);}
}
}
}
var
i,j,m:longint;
a,b,c:array[1..100]of longint;
begin
for i:=1 to 7 do
begin
readln(a[i],b[i]);
c[i]:=a[i]+b[i];
end;
for i:=1 to 7 do
if c[i]>m then
begin
m:=c[i];
j:=i;
end;
write(j);
end.