Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
c++ dfs ac 0ms#include <iostream> using namespace std; const int nxt[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int a[6][6], book[6][6], con[36][2], path[36][2], MIN = 100000000; void dfs(int x, int y, int step){ if (x == 4 && y == 4){ if (step < MIN){ MIN = step; for (int i = 0; i < MIN; ++i){ path[i][0] = con[i][0], path[i][1] = con[i][1]; } } return ; } for (int i = 0; i <= 3; ++i){ int tx = x + nxt[i][0], ty = y + nxt[i][1]; if (tx < 0 || tx > 4 || ty < 0 || ty > 4) continue; if (a[tx][ty] == 0 && book[tx][ty] == 0){ book[tx][ty] = 1; con[step][0] = tx, con[step][1] = ty; dfs(tx, ty, step + 1); book[tx][ty] = 0; } } } int main(){ ios_base::sync_with_stdio(0); for (int i = 0; i <= 4; ++i) for (int j = 0; j <= 4; ++j) cin >> a[i][j]; dfs(0, 0, 1); for (int i = 0; i < MIN; ++i) cout << '(' << path[i][0] << ", " << path[i][1] << ')' << endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator