數(shù)據(jù)結(jié)構(gòu)與算法3.1資料

Chapter3.1

StackandQueue數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第1頁(yè)。3.3TheStackADT3.3.1.StackModelAstackisalistinwhichinsertionsanddeletionstakeplaceatthesameend.Thisendiscalledthetop.Theotherendofthelistiscalledthebottom.ItisalsocalledaLIFO(last-in-first-out)list.數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第2頁(yè)。StackModeltopbottomA0An-1數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第3頁(yè)。StackModel

EtopDtopDCCBBBtopAbottomAbottomAbottom數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第4頁(yè)。StackModelAbstractDataTypeStack{

instanceslistofelements;oneendiscalledthebottom;theotheristhetop;

operations

Create():Createanemptystack;IsEmpty():Returntrueifstackisempty,returnfalseotherwiseIsFull():Returntrueifstackiffull,returnfalseotherwise;Top():returntopelementofthestack;Add(x):addelementxtothestack;Delete(x):Deletetopelementfromstackandputitinx;}

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第5頁(yè)。3.3.2.ImplementationofStack1.LinkedListImplementationofStacks^topOfStackelementnext……whentopOfStack==nullisemptystack數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第6頁(yè)。LinkedListImplementationofStackspublicclassStackLi{publicStackLi(){topOfStack=null;}publicbooleanisFull(){returnfalse;}publicbooleanisEmpty(){returntopOfStack==null;}publicvoidmakeEmpty(){topOfStack=null;}publicvoidpush(objectx)publicobjecttop()publicvoidpop()throwsUnderflowpublicobjecttopAndPop()privateListNodetopOfStack;}

ClassskeletonforlinkedlistimplementationofthestackADT數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第7頁(yè)。LinkedListImplementationofStacksSomeRoutine:publicvoidpush(objectx){topOfStack=newListNode(x,topOfStack);}publicobjecttop(){if(isEmpty())returnnull;returntopOfStack.element;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第8頁(yè)。LinkedListImplementationofStackspublicvoidpop()throwsUnderflow{if(isEmpty())thrownewUnderflow();topOfStack=topOfStack.next;}publicobjecttopAndPop(){if(isEmpty())returnnull;objecttopItem=topOfstack.element;topOfStack=topOfStack.next;returntopItem;}

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第9頁(yè)。

3.3.2.ImplementationofStack

2.ArrayImplementationofStacks

theArray

012

topOfStack

e1e2e3enwhentopOfStack==-1isemptystack數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第10頁(yè)。ArrayImplementationofStacks

publicclassstackAr{publicStackAr()publicStackAr(intcapacity)publicbooleanisEmpty(){returntopOfStack==-1;}publicbooleanisFull(){returntopOfStack==theArray.length–1;}publicvoidmakeEmpty(){topOfStack=-1;}publicvoidpush(objectx)throwsoverflowpublicobjecttop()publicvoidpop()throwsUnderflowpublicobjecttopAndPop()privateobject[]theArray;privateinttopOfStack;

staticfinalintDEFAULT_CAPACITY=10;}Stackclassskeleton---arrayimplementation數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第11頁(yè)。ArrayImplementationofStacksSomeroutine:publicStackAr(){this(DEFAULT_CAPACITY);}publicStackAr(intcapacity){theArray=newobject[capacity];topOfStack=-1;}Stackconstruction---arrayimplementation數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第12頁(yè)。ArrayImplementationofStackspublicvoidpush(objectx)throwsOverflow{if(isfull())thrownewOverflow();theArray[++topOfStack]=x;}publicobjecttop(){if(isEmpty()returnnull;returntheArray[topOfStack];}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第13頁(yè)。ArrayImplementationofStackspublicvoidpop()throwsUnderflow{if(isEmpty())thrownewUnderflow();theArray[topOfStack--]=null;}publicobjecttopAndPop(){if(isEmpty())returnnull;objecttopItem=top();theArray[topOfStack--]=null;reurntopItem;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第14頁(yè)。ArrayImplementationofStacksItiswastefulofspacewhenmultiplestacksaretocoexistWhenthere’sonlytwostacks,wecanmaintainspaceandtimeefficiencybypeggingthebottomofonestackatposition0andthebottomoftheotheratpositionMaxSize-1.Thetwostacksgrowtowardsthemiddleofthearray.數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第15頁(yè)。ArrayImplementationofStacks

0

MaxSize-1top1top2Stack1Stack2………Twostacksinanarray數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第16頁(yè)。3.3.3.Applications1.BalancingSymbols(ParenthesisMatching)2.ExpressionEvaluation數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第17頁(yè)。ParenthesisMatching

(a*(b+c)+d)(a+b))(

1234567891011

121314151617181920212223(d+(a+b)*c*(d+e)–f))(()48121611920位置不匹配

222321位置不匹配

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第18頁(yè)。#include<iostream.h>#include<string.h>#include<stdio.h>#include“stack.h”constintMaxlength=100;//maxexpressionlengthvoidPrintMatchedPairs(char*expr){Stack<int>s(Maxlength);intj,length=strlen(expr);for(inti=l;i<=length;i++){if(expr[i-1]==‘(‘)s.Add(i);elseif(expr[i-1]==‘)’)try{s.Delete(j);cout<<j<<‘‘<<i<<endl;}catch(OutOfBounds){cout<<“Nomatchforrightparenthesis”<<“at“<<i<<endl;}}while(!s.IsEmpty()){s.Delete(j);cout<<“Nomatchforleftparenthesisat“<<j<<endl;}}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第19頁(yè)。

voidstaticmain(void){charexpr[MaxLength];cout<<“typeanexpressionoflengthatmost”<<MaxLength<<endl;cin.getline(expr,MaxLength);cout<<“thepairsofmatchingparenthesesin“<<endl;puts(expr);cout<<“are”<<endl;printMatcnedPairs(expr);}O(n)

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第20頁(yè)。2.ExpressionEvaluationcompiler:infixExpressionpostfixExpressionpostfixExpressionEvaluation

A*B-C*D#AB*CD*-#(A+B)*((C-D)*E+F)#AB+CD-E*F+*#

無(wú)括號(hào)；運(yùn)算分量的次序不變；運(yùn)算符的次序就是具體執(zhí)行的次序。postfixExpressionEvaluationAB*CD*-#infixExpressionpostfixExpressionA*B-C*D#AB*CD*-#數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第21頁(yè)。postfixExpressionEvaluation

AB*CD*-#

開(kāi)辟一個(gè)運(yùn)算分量棧

1)遇分量進(jìn)棧;

2)遇運(yùn)算符:取棧頂兩個(gè)分量進(jìn)行運(yùn)算,棧中退了兩個(gè)分量,并將結(jié)果進(jìn)棧.enumBoolean{False,True};#include<math.h>#include<stack.h>#include<iostream.h>classcalculator{public:calculator(intsz):s(sz){}

voidRun();voidclear();

private:

voidAddOperand(doublevalue);BooleanGet2Operands(double&left,double&right);

voidDoOperator(charop);

stack<double>s;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第22頁(yè)。voidcalculator::AddOperand(doublevalue){s.Push(value);}Booleancalculator::Get2Operands(double&left,double&right){if(s.IsEmpty()){cerr<<“MissingOperand!”<<endl;returnfalse;}right=s.Pop();if(s.IsEmpty()){cerr<<“MissingOperand!”<<endl;returnfalse;}left=s.Pop();returntrue;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第23頁(yè)。voidcalculator::DoOperator(charop){doubleleft,right;Booleanresult;result=Get2Operands(left,right);if(result==true)

Switch(op){case‘+’:s.Push(left+right);break;

case‘-’:s.Push(left-right);break;

case‘*’:s.Push(left*right);break;case‘/’:if(right==0.0){cerr<<“divideby0!”<<endl;s.Clear();}eless.Push(left/right);break;case‘^’:s.Push(power(left,right));break;}

elses.Clear();}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第24頁(yè)。voidCalculator::Run(){charch;doublenewoperand;while(cin>>ch,ch!=‘#‘){switch(ch){case‘+’:case‘-’:case‘*’:case‘/’:case‘^’:DoOperator(ch);break;default:cin.Putback(ch);cin>>newoperand;AddOperand(newoperand);break;}}}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第25頁(yè)。voidCalculator::clear(){s.MakeEmpty();}#include<Calculator.h>voidmain(){CalculatorCALC(10);CALC.Run();}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第26頁(yè)。infixExpressionpostfixExpression

A+B*C#--------ABC*+#

1)迂運(yùn)算分量輸出

2)迂運(yùn)算符：比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先級(jí).若當(dāng)前運(yùn)算符的優(yōu)先級(jí)<=棧頂運(yùn)算符的優(yōu)先級(jí),則不斷取出運(yùn)算符棧頂輸出,否則進(jìn)棧.因此一開(kāi)始棧中要放一個(gè)優(yōu)先級(jí)最低的運(yùn)算符,假設(shè)為“#”，例子：A+B+C；A*B-C

(A+B)*(C-D)#------AB+CD-*#

3）迂‘（’:每個(gè)運(yùn)算符有雙重優(yōu)先級(jí).4）迂‘）’:5）迂‘#’:數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第27頁(yè)。infixExpressionpostfixExpression

voidpostfix(expressione){Stack<char>s;charch,y;s.MakeEmpty();s.Push(‘#’);

while(cin.get(ch),ch!=‘#’){if(isdigit(ch))cout<<ch;

elseif(ch==‘)’)

for(y=s.Pop();y!=‘(‘;y=s.Pop())cout<<y;

else

{for(y=s.Pop();isp(y)>icp(ch);y=s.Pop()) cout<<y;s.Push(y);s.Push(ch);}}

while(!s.IsEmpty()){y=s.Pop();cout<<y;}}

如果合為一步怎么做？實(shí)習(xí)題。數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第28頁(yè)。

Chapter3----stack2010年全國(guó)統(tǒng)考題1、若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（

）A：dcebfa

B：cbdaef

C：bcaefd

D：afedcb

實(shí)習(xí)題：

5.中綴表達(dá)式后綴表達(dá)式對(duì)后綴表達(dá)式求值,合為一趟來(lái)做。數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第29頁(yè)。3.4.TheQueueADT

Aqueueisalinearlistinwhichadditionsanddeletionstakeplaceatdifferentends.Itisalsocalledafirst-in-first-outlist.Theendatwhichnewelementsareaddediscalledtherear.Theendfromwhicholdelementsaredeletediscalledthefront.數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第30頁(yè)。3.4.1.QueueModel

Samplequeues

frontrearfrontrearfrontrearABCBCBCD

DeleteA

AddD數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第31頁(yè)。QueueModel

AbstractDataTypeQueue

{

instancesorderedlistofelements;oneendiscalledthefront;theotheristherear;operationsCreate():Createanemptyqueue;IsEmpty():Returntrueifqueueisempty,returnfalseotherwise;IsFull():returntrueifqueueisfull,returnfalseotherwise;First():returnfirstelementofthequeue;Last():returnlastelementofthequeue;Add(x):addelementxtothequeue;Delete(x):deletefrontelementfromthequeueandputitinx;}

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第32頁(yè)。3.4.2.ArrayImplementationofQueue

ABC……theArray:front

back012n-1

XcurrentSizethequeuesize:currentSize;anemptyqueuehascurrentSize==0;anfullqueuehascurrentSize==theArray.length;數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第33頁(yè)。3.4.2.ArrayImplementationofQueue

Toaddanelement:back=back+1;theArray[back]=x;

Todeleteanelement:twomethods:1)front=front+1;O(1)2)shiftthequeueonepositionleft. O(n)數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第34頁(yè)。3.4.2.ArrayImplementationofQueue

frontbackfrontbackfrontbackABC…BC…BCD…數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第35頁(yè)。3.4.2.ArrayImplementationofQueue

…ABCDEFrontbackFreespace數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第36頁(yè)。3.4.2.ArrayImplementationofQueue

touseacirculararraytorepresentaqueue

backCBAfrontbackCBAfrontD

Addtion數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第37頁(yè)。3.4.2.ArrayImplementationofQueue

deletionCBAfront

DbackdeletionCBfrontbackD數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第38頁(yè)。3.4.2.ArrayImplementationofQueueHowimplementationacirculararray:WhenfrontorbackreachstheArray.length-1,reset02)back=(back+1)%theArray.lengthfront=(front+1)%theArray.length數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第39頁(yè)。3.4.2.ArrayImplementationofQueuePublicclassQueueAr{publicQueueAr()publicQueueAr(intcapacity)publicbooleanisEmpty(){returncurrentsize==0;}publicbooleanisfull(){returncurrentSize==theArray.length;}publicvoidmakeEmpty()

publicObjectgetfront()publicvoidenqueue(Objectx)throwOverflowprivateintincrement(intx)

privateObjectdequeue()privateObject[]theArray;privateintcurrentSize;privateintfront;privateintback;staticfinalintDEFAULT_CAPACITY=10;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第40頁(yè)。3.4.2.ArrayImplementationofQueue

publicQueueAr(){this(DEFAULT_CAPACITY);

}publicQueueAr(intcapacity){theArray=newObject[capacity];makeEmpty();}publicvoidmakeEmpty(){currentSize=0;front=0;back=-1;}

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第41頁(yè)。3.4.2.ArrayImplementationofQueuepublicvoidenqueue(objectx)throwOverflow{if(isFull())thrownewOverflow();back=increment(back);theArray[back]=x;currentSize++;}privateintincrement(intx){if(++x==theArray.length)x=0;returnx;}

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第42頁(yè)。3.4.2.ArrayImplementationofQueuepublicObjectdequeue(){if(isEmpty())returnnull;currentSize--;ObjectfromtItem=theArray[front];theArray[front]=null;front=increment(front);returnfrontItem;}

數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第43頁(yè)。3.4.3LinkedRepresentationofqueue

Linkedqueues

datalink……^frontbacka1a2

an數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第44頁(yè)。3.4.3LinkedRepresentationofqueue

Classdefinitionforalinkedqueuetemplate<classT>classLinkedQueue{public:LinkedQueue(){front=back=0;}~LinkedQueue();boolIsEmpty()const{return((front)?false:true);}boolIsFull()const;TFirst()const;TLast()const;LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);privarte:Node<T>*front;Node<T>*back;};數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第45頁(yè)。3.4.3LinkedRepresentationofqueue1)destructortemplate<classT>LinkedQueue<T>::~LinkedQueue(){Node<T>*next;while(front){next=front.link;deletefront;front=next;}}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第46頁(yè)。3.4.3LinkedRepresentationofqueue2)Add(x)

template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){Node<T>*p=newNode<T>;p.data=x;p.link=0;

if(front)back.link=p;elsefront=p;back=p;return*this;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第47頁(yè)。3.4.3LinkedRepresentationofqueue3)Delete(x)

template<classT>LinkedQueue<T>&LinkedQueue<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=front.data;

Node<T>*p=front;front=front.link;deletep;return*this;}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第48頁(yè)。3.4.4Application1)Printthecoefficientsofthebinomialexpansion(a+b)i,i=1,2,3,…,n11121133114641151010511615201561數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第49頁(yè)。Printthecoefficientsofthebinomialexpansion#include<stdio.h>#include<iostream.h>#include“queue.h”voidYANGHUI(intn){Queue<int>q;q.makeEmpty();q.Enqueue(1);q.Enqueue(1);

ints=0;

for(inti=1;i<=n;i++){cout<<

endl;

for(intk=1;k<=10-i;k++)cout<<‘‘;q.Enqueue(0);for(intj=1;j<=i+2;j++){intt=q.Dequeue();q.Enqueue(s+t);s=t;

if(j!=i+2)cout<<s<<‘‘;}}}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第50頁(yè)。Printthecoefficientsofthebinomialexpansion用可變長(zhǎng)度的二維數(shù)組來(lái)實(shí)現(xiàn)：publicclassYanghui{publicstaticvoidmain(Stringargs[]){intn=10;intmat[][]=newint[n][];//申請(qǐng)第一維的存儲(chǔ)空間

inti,j;for(i=0;i<n;i++){mat[i]=newint[i+1];//申請(qǐng)第二維的存儲(chǔ)空間，每次長(zhǎng)度不同

mat[i][0]=1;mat[i][i]=1;for(j=1;j<i;j++)mat[i][j]=mat[i-1][j-1]+mat[i-1][j];}for(i=0;i<mat.length;i++){for(j=0;j<n-i;j++)System.out.print(““);for(j=0;j<mat[i].length;j++)System.out.print(““+mat[i][j]);System.out.println();}}}數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第51頁(yè)。2)WireRouting

abA7*7gradAwirebetweenaandb數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第52頁(yè)。2)WireRouting

ab3221112212b23485678678aDistancelabelingWirepath數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第53頁(yè)。步驟:

1.搜索過(guò)程*先從位置a(3,2)開(kāi)始,把a(bǔ)可到達(dá)的相鄰方格都表為1(表示與a相距為1).注意:具體實(shí)現(xiàn)時(shí),將a位置置為2,其它相鄰方格為a位置的值+1*然后把標(biāo)記為1的方格可到達(dá)的相鄰方格都標(biāo)記為2(表示與a相距為2).這里需要什么數(shù)據(jù)結(jié)構(gòu)?*標(biāo)記過(guò)程繼續(xù)進(jìn)行下去,直至到達(dá)b或找不到可到達(dá)的相鄰方格為止.本例中,當(dāng)?shù)竭_(dá)b時(shí),

b上的表記為9(實(shí)現(xiàn)時(shí)為9+2=11)

2.構(gòu)造a---b的路徑.從b回溯到a

.這里需要什么數(shù)據(jù)結(jié)構(gòu)?

*從b出發(fā),并將b的位置保存在path中.首先移動(dòng)到比b的編號(hào)小1的相鄰位置上(5,6)*接著再?gòu)漠?dāng)前位置繼續(xù)移動(dòng)到比當(dāng)前標(biāo)號(hào)小1的相鄰位置上.*重復(fù)這一過(guò)程,直至到達(dá)a.數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第54頁(yè)。2)WireRouting

boolFindPath(Positionstart,Positionfinish,int&PathLen,Position*&path){if((start.row==finish.row)&&(start.col==finish.col)){PathLen=0;returntrue;}for(inti=0;i<=m+1;i++){grid[0][i]=grid[m+1][i]=1;grid[i][0]=grid[i][m+1]=1;}Positionoffset[4];offset[0].row=0;offset[0].col=1;offset[1].row=1;offset[1].col=0;offset[2].row=0;offset[2].col=-1;offset[3].row=-1;offset[3].col=0;intNumOfNbrs=4;Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;數(shù)據(jù)結(jié)構(gòu)與算法3全文共60頁(yè)，當(dāng)前為第55頁(yè)。2)WireRouting

LinkedQueue<Position>Q;do{//labelneighborsofherefor(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){grid[nbr.row][nbr.col]=grid[here.row][here.col