hdu 1983 Kaitou Kid

hdu 1983 Kaitou Kid"/>

hdu 1983 Kaitou Kid

Kaitou Kid - The Phantom Thief (2)

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1161    Accepted Submission(s): 399


Problem Description 破解字迷之后，你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石，并离开展馆。整个展馆呈矩形分布，划分为N*M个区域，有唯一的入口和出口（不能从出口进入，同样不能从入口出去）。由某个区域可直接移动至相邻四个区域中的一个，且最快需要一分钟。假设Kid进入放有宝石的区域即可盗取宝石，无需耗时。问至少要封锁几个区域（可以封锁放有宝石的区域，但不能封锁入口和出口）才能保证Kid无法完成任务。
Input 输入的第一行有一个整数C，代表有C组测试数据。每组测试数据的第一行有三个整数N，M，T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图，其中包括：

'S'：入口
'E'：出口
'J'：放有宝石的区域，至少出现一次
'.'：空白区域
'#'：墙

Output 对每组测试数据，输出至少要封锁的区域数。
Sample Input

  2
5 5 5
SJJJJ
..##J
.JJJJ
.J...
EJ...
5 5 6
SJJJJ
..##J
.JJJJ
.J...
EJ...

Sample Output

  0
2

Author LL
Source 2008杭电集训队选拔赛 题目分析:dfs枚举+bfs判断,他妈的局部变量和全局变量为何在递归统一了,杭电你是怎么judge的...........!!!!!!!!!!!!Wa了一上午

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;int k,n,m,t,sx,sy;
char mp[3][15][15];
int vis[3][15][15];struct Node
{int x,y,f;
};//int dx[]={1,0,-1,0};
//int dy[]={0,1,0,-1};int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}};bool  bfs ( )
{queue<Node> q;Node no,ne;memset ( vis , -1 , sizeof ( vis ) );no.x = sx , no.y = sy , no.f = 0;q.push ( no );vis[0][sx][sy] = 0;while ( !q.empty() ){no = q.front();q.pop();if ( vis[no.f][no.x][no.y] >= t ) continue;for ( int i = 0 ; i < 4 ; i++ ){ne.x = no.x + dir[i][0] , ne.y = no.y + dir[i][1] , ne.f = no.f;if ( ne.x < 0 || ne.y >= m || ne.y < 0 || ne.x >= n )continue;if ( mp[ne.f][ne.x][ne.y]=='#' ) continue;if ( mp[ne.f][ne.x][ne.y] == 'J' ) ne.f = 1;if ( mp[ne.f][ne.x][ne.y] == 'E' && ne.f ) return false;if ( vis[ne.f][ne.x][ne.y] != -1 ) continue;q.push ( ne );vis[ne.f][ne.x][ne.y] = vis[no.f][no.x][no.y]+1;}}return true;
}bool dfs ( int n )
{if ( !n ) return bfs();for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j < m ; j++ )if ( mp[0][i][j]=='.' || mp[0][i][j] == 'J' ){char temp = mp[0][i][j];mp[0][i][j] = '#';if ( dfs(n-1) ) return true;mp[0][i][j] = temp;}return false;
}int main ( )
{scanf ( "%d" , &k );while ( k-- ){scanf ( "%d%d%d" , &n , &m , &t );for ( int i = 0 ; i < n ; i++ ){scanf ( "%s" , mp[0][i] );for ( int j = 0 ; j < m ; j++ )if ( mp[0][i][j] == 'S' ) sx = i , sy = j;strcpy ( mp[1][i] , mp[0][i] );    }int i;for ( i = 0 ; i < 4 ; i++ )if ( dfs (i) ) {printf ( "%d\n" , i );break;}i == 4 ? puts ("4" ):0;}return 0;
}

这个代码一直在wa
把n改成tot之后.....

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;int k,n,m,t,sx,sy;
char mp[3][15][15];
int vis[3][15][15];struct Node
{int x,y,f;
};//int dx[]={1,0,-1,0};
//int dy[]={0,1,0,-1};int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}};bool  bfs ( )
{queue<Node> q;Node no,ne;memset ( vis , -1 , sizeof ( vis ) );no.x = sx , no.y = sy , no.f = 0;q.push ( no );vis[0][sx][sy] = 0;while ( !q.empty() ){no = q.front();q.pop();if ( vis[no.f][no.x][no.y] >= t ) continue;for ( int i = 0 ; i < 4 ; i++ ){ne.x = no.x + dir[i][0] , ne.y = no.y + dir[i][1] , ne.f = no.f;if ( ne.x < 0 || ne.y >= m || ne.y < 0 || ne.x >= n )continue;if ( mp[ne.f][ne.x][ne.y]=='#' ) continue;if ( mp[ne.f][ne.x][ne.y] == 'J' ) ne.f = 1;if ( mp[ne.f][ne.x][ne.y] == 'E' && ne.f ) return false;if ( vis[ne.f][ne.x][ne.y] != -1 ) continue;q.push ( ne );vis[ne.f][ne.x][ne.y] = vis[no.f][no.x][no.y]+1;}}return true;
}bool dfs ( int tot )
{if ( !tot ) return bfs();for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j < m ; j++ )if ( mp[0][i][j]=='.' || mp[0][i][j] == 'J' ){char temp = mp[0][i][j];mp[0][i][j] = '#';if ( dfs(tot-1) ) return true;mp[0][i][j] = temp;}return false;
}int main ( )
{scanf ( "%d" , &k );while ( k-- ){scanf ( "%d%d%d" , &n , &m , &t );for ( int i = 0 ; i < n ; i++ ){scanf ( "%s" , mp[0][i] );for ( int j = 0 ; j < m ; j++ )if ( mp[0][i][j] == 'S' ) sx = i , sy = j;strcpy ( mp[1][i] , mp[0][i] );    }int i;for ( i = 0 ; i < 4 ; i++ )if ( dfs (i) ) {printf ( "%d\n" , i );break;}i == 4 ? puts ("4" ):0;}return 0;
}

神奇的ac了........