csu 1780 简单的图论问题? 搜索

中文题意不作赘述了
复制样例的时候就发现出了好多小空格
看了网上的题解发现输入的确有点问题需要处理一下
其他就是个正常搜索用优先队列存下node 每次最小值出队
（发个博客刷刷存在感好久没发了
  1 //#include<bits/stdc++.h>
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<cstring>
  7 #include<string>
  8 #include<ctime>
  9 #include<map>
 10 #include<set>
 11 #include<vector>
 12 #include<queue>
 13 #include<cstdlib>
 14 #include<cassert>
 15 #include<sstream>
 16 #include<stack>
 17 #include<list>
 18 #include<bitset>
 19 #define cl(a,b) memset(a,b,sizeof(a))
 20 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
 21 using namespace std;
 22 typedef long long ll;
 23 typedef long double ldb;
 24 typedef pair<int,int> pii;
 25 
 26 const int inf=0x3f3f3f3f;
 27 const int maxn=500+10;
 28 const int mod=1e7+7;
 29 const double eps=1e-8;
 30 const double pi=acos(-1);
 31 
 32 int dx[8]= {0,1,0,-1,1,-1,1,-1};
 33 int dy[8]= {1,0,-1,0,-1,1,1,-1};
 34 
 35 ll gcd(ll a,ll b){return a?gcd(b%a,a):b;}
 36 ll powmod(ll a,ll x,ll mod){ll t=1;while(x){if(x&1)t=t*a%mod;a=a*a%mod;x>>=1;}return t;}
 37 //---------------------------------------ヽ(^。^)丿
 38 
 39 int n,m,sx,sy,ex,ey;
 40 int mp[maxn][maxn];
 41 bool vis[maxn][maxn][5];
 42 
 43 struct node
 44 {
 45     int x,y,value,pre;
 46     node(int xx,int yy,int v){x=xx;y=yy;value=v;}
 47     bool operator < (const node &a) const
 48     {//我也不知道是为什么 反正这么定义是dis最小值优先
 49         return value>a.value;
 50     }
 51 };
 52 
 53 int number(char str[])
 54 {
 55     int sum=0,i=0;
 56     while(str[i]>='0'&&str[i]<='9')
 57     {
 58         sum=sum*10+(str[i]-'0');
 59         i++;
 60     }
 61     return sum;
 62 }
 63 
 64 bool judge(int x,int y,int pre)
 65 {
 66     if(x<0||x>=n) return false;
 67     if(y<0||y>=m) return false;
 68     if(vis[x][y][pre]) return false;
 69     if(mp[x][y]==-1) return false;
 70     return true;
 71 }
 72 
 73 int bfs1()
 74 {
 75     cl(vis,false);
 76     node start=node(sx,sy,mp[sx][sy]);
 77     vis[sx][sy][0]=true;
 78     priority_queue<node>q;
 79     q.push(start);
 80     while(!q.empty())
 81     {
 82         node tmp=q.top();
 83         q.pop();
 84         if(tmp.x==ex&&tmp.y==ey) return tmp.value;
 85         for(int i=0;i<4;i++)
 86         {
 87             int x=tmp.x+dx[i];
 88             int y=tmp.y+dy[i];
 89             int value=tmp.value+mp[x][y];
 90             if(judge(x,y,0))
 91             {
 92                 vis[x][y][0]=true;
 93                 node next(x,y,value);
 94                 q.push(next);
 95             }
 96         }
 97     }
 98     return -1;
 99 }
100 
101 int bfs2()
102 {
103     cl(vis,false);
104     node start=node(sx,sy,mp[sx][sy]);
105     start.pre=-1;
106     priority_queue<node>q;
107     q.push(start);
108     while(!q.empty())
109     {
110         node tmp=q.top();
111         q.pop();
112         if(tmp.x==ex&&tmp.y==ey) return tmp.value;
113         for(int i=0;i<4;i++)
114         {
115             if(i == tmp.pre) continue;
116             int x=tmp.x+dx[i];
117             int y=tmp.y+dy[i];
118             int value=tmp.value+mp[x][y];
119             if(judge(x,y,i))
120             {
121                 vis[x][y][i]=true;
122                 node next(x,y,value);
123                 next.pre=i;
124                 q.push(next);
125             }
126         }
127     }
128     return -1;
129 }
130 
131 int main()
132 {
133     int cas=1;
134     while(~scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey))
135     {
136         sx--,sy--,ex--,ey--;
137         cl(mp,-1);
138         for(int i=0;i<n;i++)
139         {
140             for(int j=0;j<m;j++)
141             {
142                 char tmp[10];
143                 scanf("%s",tmp);
144                 if(tmp[0]!='*') mp[i][j]=number(tmp);
145             }
146         }
147         printf("Case %d: %d %d
",cas++,bfs1(),bfs2());
148     }
149     return 0;
150 }/*
151 
152 4 4 1 2 3 2
153 7 10 3 9
154 * 45 6 2
155 * 8 14 *
156 21 1 * *
157 2 4 1 1 1 4
158 1 2 3 4
159 9 * * 9
160 2 4 1 1 1 4
161 1 * 3 4
162 9 9 * 9
163 
164 */