c++ 有一个Bug
程序还在运行时会出现Permission denied
仅以为戒
c++ 有一个Bug
程序还在运行时会出现Permission denied
仅以为戒
求森林数,裸的并查集
Program c; var n,i,j,ans:longint; map:array[1..100,1..2] of longint; f:array[1..100] of longint; function getfather(a:longint):longint; begin if f[a]=a then exit(a); f[a]:=getfather(f[a]); exit(f[a]); end; procedure union(a,b:longint); begin f[getfather(a)]:=f[getfather(b)]; end; begin read(n); for i:=1 to n do begin f[i]:=i; read(map[i,1],map[i,2]); for j:=1 to i-1 do if (map[i,1]=map[j,1]) or (map[i,2]=map[j,2]) then union(i,j); end; ans:=0; for i:=2 to n do if getfather(i)<>getfather(i-1) then begin inc(ans); union(i,i-1); end; writeln(ans); end.
题目大意:有一字符串S,你需要从n个字符串中选取一些来拼出这个串,第i个字符串代价为i,限制取P次,问最小代价(无解输出-1)
建立超源S=0,超汇T=n+26+1
1-n的结点为字符串 n+1-n+26的结点为字符
则可得——————————————————
从S向字符串连(最多可取数量),费用为i
从字符向T连(欲取数量)
从字符串向字符连(字符串可取该字母的数量)
得到图
跑费用……
!负数的布尔值为1.
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<string> #include<algorithm> #include<functional> #include<iostream> using namespace std; #define MAXN (200+10) #define M26 100 #define A 96 #define NONE (2139062143) int map[MAXN][MAXN]={0},cost[MAXN][MAXN]={0},stf[M26]={0}; int start=0,end,n; char s[5000]; int d[MAXN],pre[MAXN],q[MAXN*8]; bool b[MAXN]; void spfa() { memset(b,0,sizeof(b)); memset(d,127,sizeof(d)); memset(q,0,sizeof(q)); memset(pre,0,sizeof(pre)); int head=1,tail=1; q[1]=start;b[start]=1;d[start]=0; while (head<=tail) { int now=q[head]; for (int i=0;i<=end;i++) if (map[now][i]>0&&d[now]+cost[now][i]<d[i]) { d[i]=d[now]+cost[now][i]; pre[i]=now; if (!b[i]) { q[++tail]=i; b[i]=1; } } b[now]=0; head++; } } void hllp() { int totalcost=0; while (1) { spfa(); if (d[end]==NONE) break; int flow=NONE,i=end; do { flow=min(flow,map[pre[i]][i]); i=pre[i]; }while (i!=start); i=end; do { totalcost+=flow*cost[pre[i]][i]; map[pre[i]][i]-=flow; map[i][pre[i]]+=flow; i=pre[i]; }while (i!=start); } for (int i=end-27;i<end;i++) if (map[i][end]) { cout<<"-1n"; return; } cout<<totalcost<<endl; } int main() { // freopen("c.in","r",stdin); scanf("%s",s); scanf("%d",&n); int len=strlen(s); for (int i=0;i<len;i++) stf[s[i]-A]++; end=n+27; for (int i=1;i<=26;i++) map[n+i][end]=stf[i]; for (int i=1;i<=n;i++) { scanf("%s",s); scanf("%d",&map[start][i]); memset(stf,0,sizeof(stf)); for (int j=0;j<strlen(s);j++) stf[s[j]-A]++; for (int j=1;j<=26;j++) map[i][n+j]=stf[j]; cost[0][i]=i; cost[i][0]=-cost[0][i]; } /* for (int i=0;i<=end;i++) for (int j=0;j<=end;j++) if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl; */ hllp(); cout<<'n'; /* for (int i=0;i<=end;i++) for (int j=0;j<=end;j++) if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl; */ return 0; }
调色盘(pastele)
题目描述
Albus得到了一份礼物:来自Polaris的水彩油墨包。
Polaris的油墨包里面有N个颜色,现在Albus打算选其中的K种来作一幅风景画。
既然是风景画,颜色就不能太突兀。因此Albus进行了如下的定义:
每个颜色由三个属性刻画:R[i],G[i],B[i]。
两个颜色的“距离”指它们三个属性的最大差值,也就是Max(|Ri-Rj|,|Gi-Gj|,|Bi-Bj|)。
而K个颜色的距离,指的是其中任意两个颜色的最大距离。
你的任务是求出可能的最小距离。
输入
第一行两个整数N和K。
接下来N行,每行三个整数R[i],G[i],B[i]。
输出
可能的最小距离。
样例输入
5 3
6 6 4
6 2 7
3 1 3
4 1 5
6 2 6
样例输出
2
解释
选1,4,5三个颜色。
数据范围
对于10%的数据,N<=10
对于50%的数据,0<=Ri,Gi,Bi<=20,2<=K<=N<=100
对于80%的数据,0<=Ri,Gi,Bi<=50,2<=K<=N<=10000
对于100%的数据,2<=K<=N<=100000,0<=Ri,Gi,Bi<=150
a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);
容斥原理
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<functional> #include<algorithm> using namespace std; #define MAXN (150+10) #define MAXX (151) int n,k,a[MAXN][MAXN][MAXN]={0},c[MAXN][MAXN][MAXN]={0}; int Node_count(int x,int y,int z,int l) { if (z-l<0||y-l<0||z-l<0) return 0; return c[x][y][z]+c[x-l][y-l][z]+c[x][y-l][z-l]+c[x-l][y][z-l]-c[x-l][y][z]-c[x][y-l][z]-c[x][y][z-l]-c[x-l][y-l][z-l]; } int main() { freopen("pastele.in","r",stdin); freopen("pastele.out","w",stdout); scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x+1][y+1][z+1]++; } /* a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]; c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]); */ for (int x=1;x<=MAXX;x++) for (int y=1;y<=MAXX;y++) for (int z=1;z<=MAXX;z++) c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]); /* for (int i=1;i<=10;i++) for (int j=1;j<=10;j++) for (int k=1;k<=10;k++) if (c[i][j][k]) cout<<i<<' '<<j<<' '<<k<<' '<<c[i][j][k]<<endl; cout<<Node_count(6,6,6,6); */ int ans=MAXX;//成立 区间 (0 ,MAXX] for (int x=MAXX;x>=1;x--) for (int y=MAXX;y>=1;y--) for (int z=MAXX;z>=1;z--) { if (ans&&k<=Node_count(x,y,z,ans)) ans--; } cout<<ans<<endl; // while (1); return 0; }
翻转排序(sort)
题目描述
Alex得到了存放着一个1-n排列的容器。这个容器支持的唯一操作,是翻转排列的某一段。思考很久之后,他决定用以下方式让这个排列有序:
1 找到每一个极大的下降子序列(子序列要求连续)
2 对于每个长度大于1的极大下降子序列,对它进行翻转
3 如果排列依然不是有序的,转1
我们举一个例子:初始排列是(5 3 1 4 2)
一开始极大的下降子序列是(5 3 1)(4 2)
把这些序列翻转后得到1 3 5 2 4
接下来的极大下降子序列是(1)(3)(5 2)(4)
翻转后是13 2 5 4
接下来的极大下降子序列是(1)(3 2)(5 4)
翻转后是12 3 4 5,满足要求
定义翻转一个子序列的费用为1(注意一轮翻转的费用可能大于1),那么上面的费用一共是2+1+2=5。
现在,给你一个排列,你要求出对这个排列排序的费用。
另外题目保证:第一次划分时,所有极大下降子序列的长度都是偶数
输入
第一行一个整数N
第二行表示N个数的排列
输出
所需费用。如果不能排序,输出-1
样例输入
4
3 1 4 2
样例输出
3
数据范围
对于10%的数据,N<=10
对于40%的数据,N<=3000
对于100%的数据,N<=100000
可以证明一定能排序,否则一定能进行交换。
由于,第一次划分时,所有极大下降子序列的长度都是偶数,没有单个点,故之后的解尽可能在递增序列接口,长度不超过2
并且第一轮翻转之后不会有长度>=3的极长下降子序列
于是问题变成了求逆序对的个数,归并排序或者树状数组解决
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<functional> #include<algorithm> using namespace std; #define MAXN (100000+10) #define INF (0xfffffff) int n,a[MAXN]; long long ans=0; int le[MAXN],re[MAXN]; int len(int l,int r) { return r-l+1; } void mergesort(int l,int r) { if (l>=r) return; int m=(l+r)>>1; mergesort(l,m); mergesort(m+1,r); memcpy(le+1,a+l,sizeof(int)*(m-l+1)); memcpy(re+1,a+m+1,sizeof(int)*(r-m)); le[m-l+2]=re[r-m+1]=INF; int i=1,j=1; for (int k=l;k<=r;k++) if (le[i]<re[j]) { a[k]=le[i]; i++; } else { a[k]=re[j]; j++; ans+=m-l+1-(i-1); } } int main() { freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); } int h=1; for (int i=1;i<n;i++) { if (a[i]<a[i+1]) { if (h!=i) { ans++; for (int j=1;j<=(i-h+1)/2;j++) swap(a[(i+h)/2-j+( (i-h)%2 ) ],a[(i+h)/2+j]); // for (int k=1;k<=n;k++) cout<<a[k]<<' '; // cout<<endl; } h=i+1; } } if (h!=n) { ans++; int i=n; for (int j=1;j<=(i-h+1)/2;j++) swap(a[(i+h)/2-j+( (i-h)%2 ) ],a[(i+h)/2+j]); // for (int k=1;k<=n;k++) cout<<a[k]<<' '; // cout<<endl; } mergesort(1,n); cout<<ans<<endl; // while (1); return 0; }
什么是运算符的重载?
运算符与类结合,产生新的含义。
为什么要引入运算符重载?
作用:为了实现类的多态性(多态是指一个函数名有多种含义)
怎么实现运算符的重载?
方式:类的成员函数 或 友元函数(类外的普通函数)
规则:不能重载的运算符有 . 和 .* 和 ?: 和 :: 和 sizeof
友元函数和成员函数的使用场合:一般情况下,建议一元运算符使用成员函数,二元运算符使用友元函数
1、运算符的操作需要修改类对象的状态,则使用成员函数。如需要做左值操作数的运算符(如=,+=,++)
2、运算时,有数和对象的混合运算时,必须使用友元
3、二元运算符中,第一个操作数为非对象时,必须使用友元函数。如输入输出运算符<<和>>
具体规则如下:
运算符 |
建议使用 |
所有一元运算符 |
成员函数 |
= ( ) [ ] -> |
必须是成员函数 |
+= -= /= *= ^= &= != %= >>= <<= , 似乎带等号的都在这里了. |
成员函数 |
所有其它二元运算符, 例如: –,+,*,/ |
友元函数 |
<< >> |
必须是友元函数 |
2. 参数和返回值
当参数不会被改变,一般按const引用来传递(若是使用成员函数重载,函数也为const).
对于返回数值的决定:
1) 如果返回值可能出现在=号左边, 则只能作为左值, 返回非const引用。
2) 如果返回值只能出现在=号右边, 则只需作为右值, 返回const型引用或者const型值。
3) 如果返回值既可能出现在=号左边或者右边, 则其返回值须作为左值, 返回非const引用。
运算符重载举例:
+和 -运算符的重载:
调用:
总结:
1、由于+ -都是出现在=号的右边,如c=a+b,即会返回一个右值,可以返回const型值
2、后几个表达式讨论的就是,数和对象混合运算符的情况,一般出现这种情况,常使用友元函数
3、双目运算符的重载:
重载运算符函数名:operator@(参数表)
隐式调用形式:obj1+obj2
显式调用形式:obj1.operator+(OBJ obj2)---成员函数
operator+(OBJ obj1,OBJ obj2)---友元函数
执行时,隐式调用形式和显式调用形式都会调用函数operator+()
++和--运算符的重载:
函数调用:
总结:
1、a++
函数返回:temp(临时变量)
函数返回是否是const类型:返回是一个拷贝后的临时变量),不能出现在等号的左边(临时变量不能做左值),函数的结果只能做右值,则要返回一个const类型的值
++a
函数返回:*this;
函数返回是否是const类型:返回原状态的本身,返回值可以做左值,即函数的结果可以做左值,则要返回一个非const类型的值
2、前后缀仅从函数名(operator++)无法区分,只能有参数区分,这里引入一个虚参数int x,x可以是任意整数。
3、单目运算符的重载:
重载运算符函数名:operator@(参数表)
隐式调用形式:obj1@ 或 @obj1
显式调用形式:
成员函数:
obj1.operator@( )//前缀
obj1.operator@(0)//后缀
友元函数:
operator@(OBJ obj)//前缀
operator@(OBJ obj,int x)//后缀
执行时,隐式调用形式和显式调用形式都会调用函数operator@()
重载下标运算符[ ]
调用:
重载下标运算符[ ]的目的:
1、对象[x] 类似于 数组名[x],更加符合习惯
2、可以对下标越界作出判断
语法:
重载方式:只能使用成员函数重载
函数名:operator[ ](参数表)
参数表:一个参数,且仅有一个参数,该参数设定了下标值,通常为整型,但是也可以为字符串( 看成下标)。
函数调用:显式调用:Obj[arg]-对象[下标]
隐式调用:obj.operator[ ](arg)
返回类型:
1、返回函数引用 + 返回成员的实际类型(由程序员根据函数体定义)
2、因为返回值可以做左值和右值,应该不使用返回值为const类型
但是,为了能访问const对象,下标运算符重载有非const和const两个版本。(待定写)
如:int& Point::operator[](int y)//为什么使用返回引用:返回的值可以做左值,也可以做右值,则必须使用返回引用
重载运算符( )
重载运算符( )的目的:
1、对象( ) 类似于 函数名(x),更加符合习惯
语法:
重载方式:只能使用成员函数重载
重载后还可以继续重载
函数名:operator( )(参数表)
参数表:参数随意,具体根据实际情况而定。
函数调用:显式调用:Obj(x)
隐式调用:obj.operator( )(x)
返回类型:
1、返回成员的实际类型随意,具体由程序员根据函数体定义
2、因为返回值只能做右值,只读,应该使用返回值为const类型
重载输入输出操作符<< >>
语法:
重载方式:只能使用友元函数重载 且 使用三个引用&
函数名:
输出流: operator<<(参数表)
输入流:operator>>(参数表)
参数表:固定(容易出错啊),两个参数均用引用&
输出流: 必须是两个参数:对输出流ostream& 和 对象
第一个操作数cout,定义在文件iostream中,是标准类类型ostream的对象的引用。
如:ostream& cout,const Point& p
输入流:必须是两个参数:对输入流ostream& 和 对象
第一个操作数是cin,定义在文件iostream,实际上是标准类类型istream的对象的引用
如:instream& cin,const Point& p
函数调用:
输出流: 显式调用:cout<<对象
隐式调用: operator<<(cout,对象)
输入流:显式调用:cin>>对象
隐式调用: operator>>(cin,对象)
返回类型:返回类型固定 + 使用返回函数引用(满足连续输出)
输出流: 返回ostream&
如:ostream& operator<<(ostream& cout,const Point& p)
输入流:返回:istream&
如:istream& operator>>(istream& cin,Point& p)
注意:为什么输入输出操作符的重载必须使用友元函数?
因为:成员函数要求是有对象调用,则第一个参数必须是类的对象,但是<<和>>第一个参数是流的对象引用。
故,不能使用成员函数
求面积(AREA)
给出一个简单多边形(没有缺口),它的边要么是垂直的,要么是水平的。要求计算多边形的面积。
多边形被放置在一个X-Y的卡笛尔平面上,它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数(因此多边形的面积也为整数)。
输入
输入文件第一行给出多边形的顶点数n(n≤100)。接下来的几行每行给出多边形一个顶点的坐标值X和Y(都为整数并且用空格隔开)。顶点按逆时针方向逐个给出。并且多边形的每一个顶点的坐标值-200≤x,y≤200。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。
输出
输出文件仅有一行包含一个整数,表示多边形的面积。
样例
AREA.IN
10
0 0
4 0
4 1
3 1
3 3
2 3
2 2
1 2
1 3
0 3
AREA.OUT
9
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<functional> #include<algorithm> #include<queue> using namespace std; #define MAXN (100+10) class _vector { public: int x,y; _vector():x(0),y(0){} _vector(int _x,int _y):x(_x),y(_y){} friend int operator*(const _vector a,const _vector b) { return a.x*b.y-a.y*b.x; } }node[MAXN]; istream& operator>>(istream& in,_vector& a) { in>>a.x>>a.y; return in; } int n; int main() { freopen("area.in","r",stdin); freopen("area.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;i++) cin>>node[i]; node[n+1]=node[1]; int ans=0; for (int i=1;i<=n;i++) ans+=node[i]*node[i+1]; ans=abs(ans); printf("%dn",int(round(double(ans)/2))); // while (1); return 0; }
连续背包(bag)
【问题描述】
从T组物品中选出一些物品,放入背包中,求剩余空间的最小值。
限制条件:从每组物品中挑选物品必须要选取连续的一段。就是说,如果这组物品共有n个: 物品1、物品2、物品3、…、物品n,那么只能选取物品i、物品i+1、…、物品j,其中1<=i<=j<=n,或者不选。
【输入】
第一行为两个用空格隔开的正整数v和T。表示背包的空间和物品的组数。
接下来有T行,每行先是一个正整数ni,表示这组物品有ni个,然后ni个正整数,表示每个物品的大小。
【输出】
仅一个数,表示剩余空间的最小值。
【输入输出样例】
bag.in
100 3
3 7 6 8
2 80 70
4 101 108 103150
bag.out
6
【输入输出样例解释】
第1组选6、8,第2组选80,第3组不选。
【限制】
60%的数据满足:1 <= ni <= 10
100%的数据满足:1 <= ni <= 100,1<=v<=5000,1<=T<=10
对每一段背包
再对各段背包
注意单步中Vmax=V[i-1]+sum[ni]
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<functional> #include<algorithm> using namespace std; #define MAXNI (100+10) #define MAXV (500000+10) #define MAXN (10+10) int T,n,v,sum[MAXNI]={0},a[MAXNI],A[MAXN][MAXV]={0}; bool f[MAXN][MAXV]={0}; int main() { freopen("bag.in","r",stdin); freopen("bag.out","w",stdout); scanf("%d%d",&v,&T); // v=v*10; f[0][0]=1; for (int i=1;i<=T;i++) { scanf("%d",&n); sum[0]=0; for (int j=1;j<=n;j++) {scanf("%d",&a[j]);if (a[j]>v/*/10*/) a[j]=0; sum[j]=sum[j-1]+a[j];} //for (int j=1;j<=n;j++) printf("%d ",sum[j]); for (int k=0;k<=v+sum[n];k++) for (int j=n;j>=0;j--) { if (k-sum[j]<0) continue; if (f[i-1][k-sum[j]]) { f[i][k]=1; A[i][k]=j; break; } } for (int k=0;k<=v+sum[n];k++) for (int j=A[i][k]-1;j>=1;j--) { f[i][k-sum[j]]=f[i][k]||f[i][k-sum[j]]; } //cout<<endl; } // v/=10; int i=v; while (!f[T][i]) { i--; } printf("%dn",v-i); /* for (int i=0;i<=T;i++) { for (int j=0;j<=v;j++) if (f[i][j]) cout<<i<<','<<j<<' '; cout<<'n'; } while (1); */ return 0; }
水灾(sliker)
大雨应经下了几天雨,却还是没有停的样子。ksy刚从外地回来,知道不久除了自己家,其他的地方都将会被洪水淹没。
ksy的老家可以用一个N*M的地图表示,地图上有五种符号:“. * X D S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,ksy和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示ksy的家。“S”表示ksy现在的位置。
ksy每分钟可以向相邻位置移动,而洪水将会在ksy移动之后把相邻的没有的土地淹没(从已淹没的土地)。
求ksy回答家最少时间。如他回不了家,被淹死输出KAKTUS。
Input
3 3
D.*
...
.S.
Output
3
Input
3 3
D.*
...
..S
Output
KAKTUS
Input
3 6
D...*.
.X.X..
....S.
Output
6
因为第i秒走后,所到达的点不能有Flood
所以必须在之前Flood,然后再往下找
显然柯黑再同一个地方停留不优
故只要存储到达一个点的最短时间
注意C++中构造函数的写法
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<functional> #include<algorithm> #include<queue> using namespace std; #define MAXN (50+10) struct node { int x,y,t; node():x(0),y(0),t(0){} node(int _x,int _y,int _t):x(_x),y(_y),t(_t){/*cout<<x<<' '<<y<<' '<<t<<endl;*/} }start,end; /* node made_node(int i,int j,int t) { node now; now.x=i; now.y=j; now.t=t; return now; } */ int n,m; bool map[MAXN][MAXN],b[MAXN][MAXN]; char s[MAXN]; queue<node> flood,q; bool inside(int x,int y) { if (x>=1&&x<=n&&y>=1&&y<=m) return true; return false; } bool bfs() { int l=-1; while (!q.empty()) { node now=q.front(); // cout<<now.x<<' '<<now.y<<endl; q.pop(); if (now.t>l) { int size=flood.size(); while (size) { node nowf=flood.front(); flood.pop(); int x=nowf.x,y=nowf.y; if (x>1&&b[x-1][y]) { flood.push(node(x-1,y,now.t)); map[x-1][y]=b[x-1][y]=0; } if (x<n&&b[x+1][y]) { flood.push(node(x+1,y,now.t)); map[x+1][y]=b[x+1][y]=0; } if (y>1&&b[x][y-1]) { flood.push(node(x,y-1,now.t)); map[x][y-1]=b[x][y-1]=0; } if (y<m&&b[x][y+1]) { flood.push(node(x,y+1,now.t)); map[x][y+1]=b[x][y+1]=0; } size--; } l++; } int x=now.x,y=now.y; // if (!map[x][y]) continue; if (x>1&&map[x-1][y]) { if (x-1==end.x&&y==end.y){end.t=now.t+1; return true;} q.push(node(x-1,y,now.t+1)); map[x-1][y]=0; } if (x<n&&map[x+1][y]) { if (x+1==end.x&&y==end.y){end.t=now.t+1; return true;} q.push(node(x+1,y,now.t+1)); map[x+1][y]=0; } if (y>1&&map[x][y-1]) { if (x==end.x&&y-1==end.y){end.t=now.t+1; return true;} q.push(node(x,y-1,now.t+1)); map[x][y-1]=0; } if (y<m&&map[x][y+1]) { if (x==end.x&&y+1==end.y){end.t=now.t+1; return true;} q.push(node(x,y+1,now.t+1)); map[x][y+1]=0; } } return false; } int main() { freopen("sliker.in","r",stdin); freopen("sliker.out","w",stdout); scanf("%d%d",&n,&m); memset(map,1,sizeof(map)); memset(b,1,sizeof(b)); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=0;j<m;j++) { if (s[j]=='S') { start=node(i,j+1,0); q.push(start); } if (s[j]=='D') { end=node(i,j+1,0); b[i][j+1]=0; } if (s[j]=='X') { map[i][j+1]=0; b[i][j+1]=0; } if (s[j]=='*') { map[i][j+1]=0; b[i][j+1]=0; flood.push(node(i,j+1,0)); } } } /* for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (map[i][j]) cout<<"map "<<i<<' '<<j<<endl; cout<<"end"<<end.x<<' '<<end.y; */ if (bfs()) printf("%dn",end.t); else printf("KAKTUSn"); // while (1); return 0; }