2019-11-27 04:34:00 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; char s[505][505]; int v[505][505]; vector<pair<int,int>> ans; int H,W,sx,sy,gx,gy,cnt = 0; void dfs(int d,int nx,int ny,vector<pair<int,int>> way){ if(d==cnt && nx == gx && ny == gy){ ans = way; return; } int dx[4] = {0,-1,0,1}; int dy[4] = {-1,0,1,0}; for(int i=0;i<4;i++){ int tx = nx + dx[i]; int ty = ny + dy[i]; if(tx>=0 && ty>=0 && tx<H && ty<W){ if(v[tx][ty]==0 && s[tx][ty] =='0'){ v[tx][ty] = 1; way.emplace_back(tx,ty); dfs(d+1,tx,ty,way); way.pop_back(); v[tx][ty] = 0; } } } } int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W >> sx >> sy >> gx >> gy; sx--;sy--;gx--;gy--; rep(i,H)cin >> s[i]; rep(i,H)rep(j,W)if(s[i][j]=='0')cnt++; vector<pair<int,int>> tmp; tmp.emplace_back(sx,sy); v[sx][sy] = 1; dfs(1,sx,sy,tmp); v[sx][sy] = 0; cout << cnt << endl; rep(i,cnt){ cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl; } }
RECOMMEND