Second option, binary search along the diagonal, e.g. from (0,0), (1,1), ... (n,n) where n is min(max-x, max-y), until you find last pass. Call this point (p,p). If f(p+1, p) passes : binary search for last pass along x axis between [p+2...max-x]. Else if f(p,p+1) passes : binary search for last pass along the y axis between [p+2...max-y]. Else answer is (p,p) assuming I've understood your problem set correctly. If f is not too complex, and your data matrix is not large, then maybe a simple linear search is "good enough" wrt the above.
"A little song, a little dance, a little seltzer down your pants" Chuckles the clown