Please programming calculation xiaoming can go to the black floor tile at most how many piece,
Input contains multiple sets of test data,
Each group of input is first two positive integers W and H, respectively floor tile lines, (1 & lt;=W, H<=25)
The next H lines, each containing W characters, character meaning is as follows:
'. 'said black tile;
'#' said red tile;
'@', said xiao Ming standing position at the beginning, this position is a piece of black floor tile, and this character in each group of input will be only one,
When W=0, H=0, input end,
The code I wrote is
#include
using namespace std;
Const int maxn=25;
Char MPT [maxn] [maxn];
Int dirt [4], [2]={1, 0, 1,0,0,1,0, 1};
Int vis [maxn] [maxn];
Struct node {
Int x;
Int y;
};
Queue
Int BFS (int x, int sy) {
Memset (vis, 0, sizeof (vis));
The node a={sx, sy};
Int ans=1;
Q.p ush (a);
Vis [x] [sy]=1;
while(! Q.e mpty ()) {
The node b=q.f ront ();
q.pop();
for(int i=0; i<4. I++) {
Int nx=b.x + dirt [I] [0];
Int ny=b.y + dirt [I] [1];
If ((MPT [nx] [ny]=='@' | | MPT (nx) [New York]=='. ') & amp; Vis/nx (ny)==0) {
The node c={nx, ny};
Q.p ush (c);
Vis/nx] [ny]=1;
Ans++;
}
}
}
Return ans.
}
Int main () {
Int m, n;
While (cin> M> N) {
If (m==0 & amp; N==0) {
break;
}
The else
Memset (MPT, 0, sizeof (MPT));
Memset (vis, 0, sizeof (vis));
while(! Q.e mpty ()) {
q.pop();
}
for(int i=1; i<=m; I++) {
For (int j=1; j<=n; J++) {
cin> MPT [I] [j];
}
}
Int k, l;
for(int i=1; i<=m; I++) {
For (int j=1; j<=n; J++) {
If (MPT [I] [j]=='@') {
K=I;
L=j;
}
}
}
Int ans=BFS (k, l);
cout
return 0;
}
Bosses and see where the problem is
CodePudding user response:
Or learnThe depth of the lookup algorithm!
Do simple point
CodePudding user response:
#include
#include
#include
using namespace std;
//define state
Struct Status {
Int x;
Int y;
};
//save map
Char map [25] [25];
Each point in the//symbol map is been visited if the visit is to true
Bool mark [25] [25];
//four directions - & gt; The up and down or so
Int go [], [2]={
1, 0,
1, 0,
0, 1,
0, 1
};
QueueQ;
Bool check (int x, int y, int H, int W) {//check whether position (x, y) can access
If (x<1 | | x> H | | y<1 | | y> W | | mark [x] [y]==true | | map [x] [y]=='#') {
return false;
}
return true;
}
//use references to save the answer
Void BFS (int & amp; Ret, int H, int W)
{
while (! Q.e mpty ()) {
The Status of cur=Q.f ront ();
Q.p op ();
Ret++;
for (int i=0; i <4. I++) {//get the current position of the next position there are four possible levels of
Int nx=cur. X + go [I] [0];//the next position coordinates x
Int ny=cur. Y + go [I] [1];//the next position y
The Status of t;//generated new state
T.x=nx;
T.y Lin=ny;
If (check (nx, ny, H, W)) {//if the new state conforms to the requirements team
Q.p ush (t);
Mark (nx) [New York]=true; Has been visited//marked as
}
}
}
}
Int main ()
{
Int W, H;
While (the scanf (" % d % d ", & amp; W, & amp; H)! EOF)={
Getchar (); Kill input//W, H after the enter
If (W==0 & amp; & H==0) break;
//to empty the last input
for (int i=0; i <25. I++) {
For (int j=0; J & lt; 25. J++) {
Mark [I] [j]=false;
The map [I] [j]=0;
}
}
while (! Q.e mpty ()) {
Q.p op ();
}
//into the input
For (int I=1; i <=H; I++) {//in accordance with each line directly to lose in
The scanf (" % s ", the map [I] + 1);//note here % s map [I] + 1
}
//initialize
The Status the head;
For (int I=1; i <=H; I++) {
For (int j=1; J & lt;=W; J++) {
If (map [I] [j]=='@') {
Head. X=I;
Head. The y=j;
Mark [I] [j]=true;
}
}
}
Q.p ush (head);
//ret used to hold the answer
Int ret=0;
//BFS function called
BFS (ret, H, W);
Printf (" % d \ n ", ret);
}
return 0;
}
This problem after understanding the BFS algorithm can quickly write, personal feel DFS and BFS is transitions between states, is moving from one state to another state, so I first defined state, concrete matters and see the code above,
CodePudding user response:
[/face
,, I solved the problem, is the line I into the ranks of the input format requirements,,,