@[Summer_Light](/space/show?uid=87668) 不要
by chen_zhe @ 2018-05-20 21:13:49
我自己还没弄出来2333
by nanatsuhi @ 2018-05-20 21:14:33
。。。凉了
by nanatsuhi @ 2018-05-20 21:15:09
本人代码
#include<bits/stdc++.h>
using namespace std;
const int desx[8]={-1,-1,0,1,1,1,0,-1};
const int desy[8]={0,1,1,1,0,-1,-1,-1};
char a[1005][1005];
int flag[1005][1005];
int dis[1005][1005];
struct node
{
int x,y,steps;
bool operator< (const node &b)const
{
return steps>b.steps;
}
};
int main ()
{
int r,c;
while (scanf("%d%d",&r,&c)==2)
{
memset(a,'\0',sizeof(a));
for(int i=0;i<r;i++)
scanf("%s",a[i]);
int m;
scanf("%d",&m);
while (m--)
{
memset(flag,0,sizeof(flag));
memset(dis,-1,sizeof(dis));
node start,end;
scanf("%d %d %d %d",&start.x,&start.y,&end.x,&end.y);
start.x--;
start.y--;
end.x--;
end.y--;
start.steps=0;
priority_queue <node> q;
q.push(start);
int ans,tx,ty,i;
node temp,cur;
flag[start.x][start.y]=1;
while (!q.empty())
{
cur=q.top();
q.pop();
if(cur.x==end.x&&cur.y==end.y)
{
ans=cur.steps;
break;
}
for(i=0;i<8;i++)
{
tx=cur.x+desx[i];
ty=cur.y+desy[i];
if(tx<r&&tx>=0&&ty<c&&ty>=0)
{
temp.x=tx;
temp.y=ty;
temp.steps=cur.steps;
if(i!=a[cur.x][cur.y]-'0')
temp.steps++;
if(temp.steps<dis[tx][ty]||dis[tx][ty]==-1)
{
dis[tx][ty]=temp.steps;
q.push(temp);
}
}
}
}
printf("%d\n",ans);
}
}
}
by xuyanze @ 2018-05-22 21:34:36