以前看杭電課件的時候，似懂非懂的把課件上的代碼打了一遍，就交上去了，然後擱置起來，不了了之，昨天飄誼童鞋在糾結這個題，就想也嘗試自己寫一遍，不寫不知道，一寫下一跳，神馬也不會，Orz……
思路：深搜+剪枝（多重剪枝）
我的AC代碼:
[cpp]
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
char map[9][9],step;
bool escape;
int e_x,e_y,s,t,dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void DFS(int x,int y,int step1)
{
if(x<=0||y<=0||x>s||y>t) //出界
return ;
if( escape == 1 ) //已搜到,退出
return ;
int temp=(step-step1)-abs(x-e_x)-abs(y-e_y); //奇偶性剪枝 && 最優性剪枝
if(temp<0||temp&1)
return;
if(x==e_x && y==e_y) //搜到終點
{
if(step1==step)
escape=1;
return ;
}
for(int i=0;i<4;i++){
if( map[x+dir[i][0]][y+dir[i][1]] != 'X' ) //深搜
{
map[x+dir[i][0]][y+dir[i][1]]= 'X';
DFS(x+dir[i][0],y+dir[i][1],step1+1);
map[x+dir[i][0]][y+dir[i][1]]='.';
}
}
return ;
}
int main(){
int i,j,s_x,s_y;
while(~scanf("%d%d%d",&s,&t,&step),s+t+step)
{
memset(map,0,sizeof(map));
for(i=1;i<=s;i++)
{
getchar();
for(j=1;j<=t;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='S')
{ s_x=i; s_y=j; }
if(map[i][j]=='D')
{ e_x=i; e_y=j; }
}
}
getchar(); //這個字符問題如果最後沒有吸收,會判錯,不知道杭電是怎樣判題的
escape=0;
map[s_x][s_y]='X'; //一定要標記,否則會搜回來
DFS(s_x,s_y,0 );
if(escape)
puts("YES");
else
puts("NO");
}
return 0;
}
課件提供代碼:
[cpp]
#include<stdio.h>
# include <iostream>
# include <string.h>
# include <stdlib.h>
using namespace std;
char map[9][9];
int n,m,t,di,dj;
bool escape;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void dfs(int si,int sj,int cnt)
{
int i,temp;
if(si>n||sj>m||si<=0||sj<=0) return;
if(cnt==t&&si==di&&sj==dj) escape=1;
if(escape) return;
temp=(t-cnt)-abs(si-di)-abs(sj-dj);
if(temp<0||temp&1) return;
for(i=0;i<4;i++){
if(map[si+dir[i][0]][sj+dir[i][1]]!='X')
{
map[si+dir[i][0]][sj+dir[i][1]]='X';
dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
map[si+dir[i][0]][sj+dir[i][1]]='.';
}
}
return;
}
int main()
{
freopen("Input.txt","r",stdin);
freopen("Output.txt","w",stdout);
int i,j,si,sj;
while(cin>>n>>m>>t)
{
if(n==0&&m==0&&t==0) break;
int wall=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S') { si=i; sj=j; }
else if(map[i][j]=='D') { di=i; dj=j; }
else if(map[i][j]=='X') wall++;
}
if(n*m-wall<=t)
{
cout<<"NO"<<endl;
continue;
}
escape=0;
map[si][sj]='X';
dfs(si,sj,0);
if(escape) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
測試數據生成器:
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
freopen("Input.txt","w",stdout);
int n=110;
srand(time(NULL));
while(n--)
{
int x,y,z,i,j,temp;
x=rand()%6+2;
y=rand()%6+2;
z=rand()%(x*y)+1;
printf("%d %d %d\n",x,y,z);
for(i=1;i<=x;i++)
{
for(j=1;j<=y;j++)
{
if(i==x&&j==y)
printf("S");
else if(i==x/2&&j==y/2)
printf("D");
else
{
switch(rand()%6)
{
case 0:case 1:case 2:case 3:case 4:printf(".");break;
case 5:printf("X");
}
}
}
printf("\n");
}
}
return 0;
}
對拍程序:
[cpp]
#include<stdio.h>
#include<string.h>
int main()
{
char a[120][5],b[120][5];
int i=0,j=0;
freopen("Output.txt","r",stdin);
while(~scanf("%s",a[i]))i++;
freopen("Output1.txt","r",stdin);
while(~scanf("%s",b[j]))j++;
for(i=0;i<j;i++)
if(strcmp(a[i],b[i])!=0)
printf("%d\n",i);
return 0;
}
作者：ice2013
