首页 > 代码库 > HDU 2579 Dating with girls(2) BFS 余数判重
HDU 2579 Dating with girls(2) BFS 余数判重
对于石头的处理就按照每个位置的时间取k的余数判一下重复就好,其他随意写
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> pii;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 105;const int maxk = 10;const int dx[] = {0,0,1,-1};const int dy[] = {1,-1,0,0};int d[maxn][maxn][maxk];int n,m,k,sx,sy,ex,ey;char mp[maxn][maxn];void bfs() { queue<int> qx,qy,qk; qx.push(sx); qy.push(sy); qk.push(0); d[sx][sy][0] = 0; int x,y,nowk,nx,ny,nk; while(!qx.empty()) { x = qx.front(); y = qy.front(); nowk = qk.front(); qx.pop(); qy.pop(); qk.pop(); int nowt = d[x][y][nowk]; for(int i = 0;i < 4;i++) { nx = x + dx[i]; ny = y + dy[i]; nk = (nowk + 1) % k; int &nt = d[nx][ny][nk]; if((nk == 0 || mp[nx][ny] != ‘#‘) && nt > nowt + 1) { if(nx < 1 || nx > n || ny < 1 || ny > m) continue; nt = nowt + 1; qx.push(nx); qy.push(ny); qk.push(nk); } } }}int main() { int T; scanf("%d",&T); while(T--) { memset(mp,‘#‘,sizeof(mp)); memset(d,0x3f,sizeof(d)); int inf = d[0][0][0]; scanf("%d%d%d",&n,&m,&k); for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { scanf(" %c",&mp[i][j]); if(mp[i][j] == ‘Y‘) { sx = i; sy = j; } if(mp[i][j] == ‘G‘) { ex = i; ey = j; } } } bfs(); int ans = inf; for(int i = 0;i < k;i++) ans = min(ans,d[ex][ey][i]); if(ans < inf) printf("%d\n",ans); else puts("Please give me another chance!"); } return 0;}
HDU 2579 Dating with girls(2) BFS 余数判重
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。