Question

杭电 ACM 1010 WA了 求助

#include <iostream>
using namespace std;
const int MAXN = 8;
char maze[MAXN][MAXN];
bool v[MAXN][MAXN];
int n,m,limit,wall;
int startx,starty,endx,endy;
bool escape;

int iX[4]={1,0,-1,0};
int iY[4]={0,1,0,-1};

void Work_DFS(int x,int y,int t)
{
int newx,newy,tmp;
if(t > limit)return ;
tmp = limit - t - abs(startx - endx) - abs(starty - endy);
if(tmp < 0){
escape = false;
return;
}
if(x == endx && y == endy && t == limit){
escape=true;
return;
}
v[x][y] = true;
for(int i = 0;i < 4;i++){
newx = x + iX[i];
newy = y + iY[i];
if(newx >= 0 && newx < n && newy > 0 && newy < m && maze[newx][newy] != 'X'&& v[newx][newy] == false)
Work_DFS(newx,newy,t+1);
}
v[x][y] = false;
}

void Input()
{
scanf("%d%d%d",&n,&m,&limit);
while(n != 0 && m != 0 && limit != 0){
memset(v,false,sizeof(v));
escape=false;
wall=0;
for(int i = 0;i < n;i++)scanf("%s",maze[i]);
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++){
if(maze[i][j] == 'S'){
startx = i;
starty = j;
}
if(maze[i][j] == 'D'){
endx = i;
endy = j;
}
if(maze[i][j]=='X')wall++;
}
if(!(n * m - wall < limit))Work_DFS(startx,starty,0);
if(escape)printf("YES\n");
else printf("NO\n");
scanf("%d%d%d",&n,&m,&limit);
}
}

int main()
{
Input();
system("pause");
return 0;
}

Answer 1

#include <iostream>
using namespace std;
const int MAXN = 8;
char maze[MAXN][MAXN];
bool v[MAXN][MAXN];
int n,m,limit,wall;
int startx,starty,endx,endy;
bool escape;

int iX[4]={1,0,-1,0};
int iY[4]={0,1,0,-1};

void Work_DFS(int x,int y,int t)
{
if(escape) return; // 成功逃出则不要继续DFS
int newx,newy,tmp;
if(t > limit)return ;
tmp = limit - t - abs(x - endx) - abs(y - endy); // 应该是x-endx和y-endy
if(tmp < 0){
//escape = false; // 不能设定false
return;
}
if(x == endx && y == endy && t == limit){
escape=true;
return;
}
v[x][y] = true;
for(int i = 0;!escape&&i < 4;i++){ // 如果escape了就不再DFS
newx = x + iX[i];
newy = y + iY[i];
if(newx >= 0 && newx < n && newy >= 0 && newy < m && maze[newx][newy] != 'X'&& v[newx][newy] == false)
Work_DFS(newx,newy,t+1);
}
v[x][y] = false;
}

void Input()
{
scanf("%d%d%d",&n,&m,&limit);
while(n != 0 || m != 0 || limit != 0){
memset(v,false,sizeof(v));
escape=false;
wall=0;
for(int i = 0;i < n;i++)scanf("%s",maze[i]);
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++){
if(maze[i][j] == 'S'){
startx = i;
starty = j;
}
if(maze[i][j] == 'D'){
endx = i;
endy = j;
}
if(maze[i][j]=='X')wall++;
}
if(!(n * m - wall < limit+1)&&(startx + endx + starty + endy + limit)%2==0) // 如果步差和limit奇偶性不同, 或者可行走部分少于limit+1, 则不用DFS
Work_DFS(startx,starty,0);
if(escape)printf("YES\n");
else printf("NO\n");
scanf("%d%d%d",&n,&m,&limit);
}
}

int main()
{
Input();
//system("pause");
return 0;
}

Answer 2

什么东东

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <mem.h>
#include <math.h>
用的都是C库,包含C++的有啥用